Article

Free access

Window query-optimal clustering of spatial objects

Authors:

Bernd-Uwe Pagel,

Hans-Werner Six,

Mario WinterAuthors Info & Claims

PODS '95: Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

Pages 86 - 94

https://doi.org/10.1145/212433.212458

Published: 22 May 1995 Publication History

PDF eReader

References

[1]

N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: an efficient and robust access method for points and rectangles. In Proc. A CM SIGMOD Int. Conf. on Management of Data, Atlantic City, 1990.

Digital Library

Google Scholar

[2]

L. Bachmann, B.-U. Pagel, and H.-W. Six. Optimizing spatial data structures for static data. In Proc. Int. Workshop on Advanced Research in Geographic Informatzon Systems, pages 247-258. Springer LNCS Vol. 884, March 1994.

Digital Library

Google Scholar

[3]

M.R. Garey and D.S. Johnson. Complexity results for multiprocessor scheduling under resource constraints. SIAM J. Comput., 4:387-411, 1975.

Google Scholar

[4]

M. GrStschel, L. Lovasz, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169-197, 1981.

Crossref

Google Scholar

[5]

A. Guttman. R-trees: a dynamic index structure for spatial searching. In Proc. A CM SIGMOD Int. Conf. on Management of Data, pages 47-57, Boston, 1984.

Digital Library

Google Scholar

[6]

K.A. Hua, S.D. Lang, and W.K. Lee. A decomposition-based simulated annealing technique for data clustering. In Proc. A CM Symposium on Principles on Database Systems, pages 117-128, Minneapolis, Minnesota, 1994.

Digital Library

Google Scholar

[7]

A. Henrich, H.-W. Six, and P. Widmayer. The LSD-tree' spatial access to multidimensional point- and non-point objects. In 15th Int. Conf. on VLDB, pages 45-53, Amsterdam, 1989.

Digital Library

Google Scholar

[8]

Y.E. Ioannidis and Y.C. Kang. Randomized algorithms for optimizing large join queries. In Proc. A CM SIGMOD Int. Conf. on Management of Data, pages 312-321, Atlantic City, NJ, 1990.

Digital Library

Google Scholar

[9]

Y.E. Ioannidis and E. Wong. Query optimization by simulated annealing. In Proc. ACM SIGMOD Int. Conf. on Management o/ Data, pages 9-22, San Francisco, CA, 1987.

Digital Library

Google Scholar

[10]

I. Kamel and C. Faloutsos. On packing R- trees. In Proc. 2nd Int. Conf. on Information and Knowledge Management, pages 490-499, Washington D.C., 1993.

Digital Library

Google Scholar

[11]

E.L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rhinehart and Winston, 1976.

Google Scholar

[12]

J.-L. Lutton and E. Bonomi. Simulated annealing algorithm for the minimum weighted perfect euclidean matching problem. R.A.LR.O. Recherche opdrationnelle, 20:177-197, 1986.

Crossref

Google Scholar

[13]

F.J. McErlean, D.A. Bell, and S.I. McClean. The use of simulated annealing for clustering data in databases. Information Systems, 15(2):233-245, 1990.

Digital Library

Google Scholar

[14]

B. Meyer. Eiffel: The Language. Prentice Hall, 1991.

Digital Library

Google Scholar

[15]

B.-U. Pagel, H.-W. Six, and H. Toben. The transformation technique for spatial objects revisited. In D. Abel and B.-C. Ooi, editors, Proc. 3rd Int. Symposium on Large Spatial Databases (SSD), pages 73-88, Singapore, June 1993. LNCS No. 692, Springer.

Digital Library

Google Scholar

[16]

B.-U. Pagel, H.-W. Six, H. Toben, and P. Widmayer. Towards an analysis of range query performance in spatial data structures. In Proc. A CM PODS Symposium on Prznc#ples of Database Systems), pages 214- 221, Washington, D.C., May 1993.

Digital Library

Google Scholar

[17]

M. Stonebraker, j. Frew, K. Gardels, and J. Meredith. The SEQUOIA 2000 storage benchmark. In Proc. A CM SIGMOD Int. Conf. on Management of Data, pages 2-9, Washington, D.C., May 1993.

Digital Library

Google Scholar

[18]

A. Swami. Optimization of large join queries: Combining heuristics and combinatorial techniques. In Proc. A CM SIGMOD Int. Conf. on Management of Data, pages 367-376, Portland, Oregon# 1989.

Digital Library

Google Scholar

[19]

P.J.M. van Laarhoven and E.H.L. Aarts. Szmulated Annealing: Theory and Applications. Kluwer Academic Publishers, Dordrecht, 1987.

Digital Library

Google Scholar

Cited By

View all

Liu YHuangfu WZhang HLong K(2018)Above-Threshold Queries of Environmental Conditions Based on Bilinear Interpolation in Wireless Sensor NetworksSensors10.3390/s1812420318:12(4203)Online publication date: 30-Nov-2018
https://doi.org/10.3390/s18124203
Koes DCamacho C(2015)Indexing volumetric shapes with matching and packingKnowledge and Information Systems10.1007/s10115-014-0729-z43:1(157-180)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1007/s10115-014-0729-z
Huang YLin L(2011)Evaluating K-Best Site Query on Spatial ObjectsNetworked Digital Technologies10.1007/978-3-642-22185-9_21(240-250)Online publication date: 2011
https://doi.org/10.1007/978-3-642-22185-9_21
Show More Cited By

Index Terms

Recommendations

Query directed clustering

This paper identifies the conditions under which web page clustering algorithms are effective and identifies the problems that cause them to fail. It then presents Query Directed Clustering (QDC), a web page clustering algorithm that produces higher-...
Spatial entropy-based clustering for mining data with spatial correlation
PAKDD'11: Proceedings of the 15th Pacific-Asia conference on Advances in knowledge discovery and data mining - Volume Part I

Due to the inherent characteristics of spatial datasets, spatial clustering methods need to consider spatial attributes, nonspatial attributes and spatial correlation among non-spatial attributes across space. However, most existing spatial clustering ...
Clustering in Dynamic Spatial Databases

Efficient clustering in dynamic spatial databases is currently an open problem with many potential applications. Most traditional spatial clustering algorithms are inadequate because they do not have an efficient support for incremental clustering.In ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODS '95: Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

May 1995

300 pages

ISBN:0897917308

DOI:10.1145/212433

Chairman:
Mihalis Yannakakis
AT&T Bell Labs.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 May 1995

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS95

Sponsor:

SIGMOD/PODS95: Joint ACM SIGMOD Intl Conference on Management of Data and ACM SIGACT-SIGMOD- SIGART Symposium on Principles of Database Systems

May 22 - 25, 1995

California, San Jose, USA

Acceptance Rates

PODS '95 Paper Acceptance Rate 25 of 94 submissions, 27%;

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
332
Total Downloads

Downloads (Last 12 months)31
Downloads (Last 6 weeks)3

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Liu YHuangfu WZhang HLong K(2018)Above-Threshold Queries of Environmental Conditions Based on Bilinear Interpolation in Wireless Sensor NetworksSensors10.3390/s1812420318:12(4203)Online publication date: 30-Nov-2018
https://doi.org/10.3390/s18124203
Koes DCamacho C(2015)Indexing volumetric shapes with matching and packingKnowledge and Information Systems10.1007/s10115-014-0729-z43:1(157-180)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1007/s10115-014-0729-z
Huang YLin L(2011)Evaluating K-Best Site Query on Spatial ObjectsNetworked Digital Technologies10.1007/978-3-642-22185-9_21(240-250)Online publication date: 2011
https://doi.org/10.1007/978-3-642-22185-9_21
Beckmann NSeeger BÇetintemel UZdonik SKossmann D(2009)A revised r*-tree in comparison with related index structuresProceedings of the 2009 ACM SIGMOD International Conference on Management of data10.1145/1559845.1559929(799-812)Online publication date: 29-Jun-2009
https://dl.acm.org/doi/10.1145/1559845.1559929
Jeong SKim SChoi B(2009)Dimensionality reduction for similarity search with the Euclidean distance in high-dimensional applicationsMultimedia Tools and Applications10.1007/s11042-008-0243-y42:2(251-271)Online publication date: 1-Apr-2009
https://dl.acm.org/doi/10.1007/s11042-008-0243-y
Jeong SKim SChoi B(2007)Dimensionality reduction in high-dimensional space for multimedia information retrievalProceedings of the 18th international conference on Database and Expert Systems Applications10.5555/2395856.2395908(404-413)Online publication date: 3-Sep-2007
https://dl.acm.org/doi/10.5555/2395856.2395908
Saita CLlirbat F(2004)Clustering Multidimensional Extended Objects to Speed Up Execution of Spatial QueriesAdvances in Database Technology - EDBT 200410.1007/978-3-540-24741-8_24(403-421)Online publication date: 2004
https://doi.org/10.1007/978-3-540-24741-8_24
Kim TLi K(2003)A distance-based packing method for high dimensional dataProceedings of the 14th Australasian database conference - Volume 1710.5555/820085.820115(135-144)Online publication date: 1-Jan-2003
https://dl.acm.org/doi/10.5555/820085.820115
Tao YPapadias D(2002)Adaptive index structuresProceedings of the 28th international conference on Very Large Data Bases10.5555/1287369.1287406(418-429)Online publication date: 20-Aug-2002
https://dl.acm.org/doi/10.5555/1287369.1287406
Song JWhang KLee YLee MHan WPark B(2002)The clustering property of corner transformation for spatial database applicationsInformation and Software Technology10.1016/S0950-5849(02)00026-544:7(419-429)Online publication date: May-2002
https://doi.org/10.1016/S0950-5849(02)00026-5
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Query directed clustering

Spatial entropy-based clustering for mining data with spatial correlation

Clustering in Dynamic Spatial Databases