Article

iTopN: incremental extraction of the N most visible objects

Authors:

Linas Bukauskas,

Leo Mark,

Edward Omiecinski,

Michael H. BöhlenAuthors Info & Claims

CIKM '03: Proceedings of the twelfth international conference on Information and knowledge management

Pages 461 - 468

https://doi.org/10.1145/956863.956949

Published: 03 November 2003 Publication History

Get Access

Abstract

The visual exploration of large databases calls for a tight coupling of database and visualization systems. Current visualization systems typically fetch all the data and organize it in a scene tree, which is then used to render the visible data. For immersive data explorations, where an observer navigates in a potentially huge data space and explores selected data regions this approach is inadequate. A scalable approach is to make the database system observer-aware and exchange the data that is visible and most relevant to the observer.In this paper we present iTopN an incremental algorithm for extracting the most visible objects relative to the current position of the observer. We implement iTopN and compare it to an improved version of the R-tree that extends LRU with the caching of the top levels of the R-tree (LW-LRU). Our experiments show that iTopN is orders of magnitude faster than LW-LRU given the same amount of memory. Our experiments also show that for LW-LRU to perform as fast as iTopN it needs three times as much memory.

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 Proceedings of ACM SIGMOD International Conference on Management of Data pages 322--331. ACM Press, 1990.

Digital Library

Google Scholar

[2]

S. Berchtold, D. A. Keim, and H.-P. Kriegel. The x-tree: An index structure for high-dimensional data. In Proceedings of 22th International Conference on Very Large Data Bases, pages 28--39. Morgan Kaufmann, 1996.

Digital Library

Google Scholar

[3]

M. Böhlen, L. Bukauskas, P. S. Eriksen, S. L. Lauritzen, A. Mažeika, P. Musaeus, and P. Mylov. 3D Visual Data Mining: Goals and Experiences. In Journal Computational Statistics & Data Analysis, of the International Association of Statistical Computing, 43, pages 445--469, Elsevier Science, 2003.

Crossref

Google Scholar

[4]

A. Guttman. R-trees: A dynamic index structure for spatial searching. In SIGMOD'84, Proceedings of Annual Meeting, pages 47--57. ACM Press, 1984.

Digital Library

Google Scholar

[5]

J. M. Hellerstein, J. F. Naughton, and A. Pfeffer. Generalized search trees for database systems. In Proceedings of 21th International Conference on Very Large Data Bases, pages 562--573. Morgan Kaufmann, 1995.

Digital Library

Google Scholar

[6]

A. Henrich. The lsdh-tree: An access structure for feature vectors. In Proceedings of 14th International Conference on Data Engineering, pages 362--369. IEEE Computer Society, 1998.

Digital Library

Google Scholar

[7]

M. Kofler, M. Gervautz, and M. Gruber. R-trees for organizing and visualizing 3d gis databases. Journal of Visualization and Computer Animation, 11(3), pages 129--143, 2000.

Crossref

Google Scholar

[8]

J. T. Robinson. The k-d-b-tree: A search structure for large multidimensional dynamic indexes. In Proceedings of ACM SIGMOD International Conference on Management of Data, pages 10--18. ACM Press, 1981.

Digital Library

Google Scholar

[9]

L. Shou, J. Chionh, Z. Huang, K.-L. Tan, and Y. Ruan. Walking through a very large virtual environment in real-time. In Proceedings of the 27th International Conference on Very Large Data Bases, pages 401--410. Morgan Kaufmann, 2001.

Digital Library

Google Scholar

[10]

Z. Song and N. Roussopoulos. K-nearest neighbor search for moving query point. In Advances in Spatial and Temporal Databases, 7th International Symposium, SSTD, pages 79--96. Springer, 2001.

Digital Library

Google Scholar

[11]

Y. Tao and D. Papadias. Time-parameterized queries in spatio-temporal databases. In Proceedings of ACM SIGMOD International Conference on Management of Data, pages 334--345. ACM Press, 2002.

Digital Library

Google Scholar

[12]

G. Varadhan and D. Manocha. Out-of-core rendering of massive geometric environments. In Proceedings of the Conference on Visualization '02, pages 69--76. IEEE Press, 2002.

Digital Library

Google Scholar

[13]

S. Šaltenis, C. S. Jensen, S. T. Leutenegger, and M. A. Lopez. Indexing the positions of continuously moving objects. In Proceedings of ACM SIGMOD International Conference on Management of Data, volume 29, pages 331--342. ACM Press, 2000.

Digital Library

Google Scholar

[14]

D. A. White and R. Jain. Similarity indexing with the ss-tree. In Proceedings of the 12th International Conference on Data Engineering, pages 516--523. IEEE Computer Society, 1996.

Digital Library

Google Scholar

Cited By

View all

Kazemi LBanaei-Kashani FShahabi CJain R(2010)Efficient approximate visibility query in large dynamic environmentsProceedings of the 15th international conference on Database Systems for Advanced Applications - Volume Part I10.1007/978-3-642-12026-8_17(202-217)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.1007/978-3-642-12026-8_17
Budvytyte SBukauskas L(2006)Location-based story telling for mobile tourist2006 7th International Baltic Conference on Databases and Information Systems10.1109/DBIS.2006.1678500(220-228)Online publication date: 2006
https://doi.org/10.1109/DBIS.2006.1678500
Bukauskas LBohlen M(2004)Query load balancing for incremental visible object extractionProceedings. International Database Engineering and Applications Symposium, 2004. IDEAS '04.10.1109/IDEAS.2004.1319808(344-353)Online publication date: 2004
https://doi.org/10.1109/IDEAS.2004.1319808

Index Terms

iTopN: incremental extraction of the N most visible objects
1. Information systems
  1. Information retrieval
    1. Evaluation of retrieval results
      1. Relevance assessment
  2. Information systems applications
    1. Data mining

Recommendations

Pipeline rendering: interaction and realism through hardware-based multi-pass rendering
Global illumination models for volume rendering
Precomputed illuminance composition for real-time global illumination
I3D '16: Proceedings of the 20th ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games

In this paper we present a new real-time approach for indirect global illumination under dynamic lighting conditions. We use surfels to gather a sampling of the local illumination and propagate the light through the scene using a hierarchy and a set of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

CIKM '03: Proceedings of the twelfth international conference on Information and knowledge management

November 2003

592 pages

ISBN:1581137230

DOI:10.1145/956863

General Chair:
Donald Kraft
Louisiana State University
,
Program Chairs:
Ophir Frieder
Illinois Institute of Technology
,
Joachim Hammer
University of Florida
,
Sajda Qureshi
University of Nebraska, Omaha
,
Len Seligman
The MITRE Corporation

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: 03 November 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CIKM03

Sponsor:

CIKM03: 12th International Conference on Information and Knowledge Management

November 3 - 8, 2003

LA, New Orleans, USA

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
340
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)1

Reflects downloads up to 09 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kazemi LBanaei-Kashani FShahabi CJain R(2010)Efficient approximate visibility query in large dynamic environmentsProceedings of the 15th international conference on Database Systems for Advanced Applications - Volume Part I10.1007/978-3-642-12026-8_17(202-217)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.1007/978-3-642-12026-8_17
Budvytyte SBukauskas L(2006)Location-based story telling for mobile tourist2006 7th International Baltic Conference on Databases and Information Systems10.1109/DBIS.2006.1678500(220-228)Online publication date: 2006
https://doi.org/10.1109/DBIS.2006.1678500
Bukauskas LBohlen M(2004)Query load balancing for incremental visible object extractionProceedings. International Database Engineering and Applications Symposium, 2004. IDEAS '04.10.1109/IDEAS.2004.1319808(344-353)Online publication date: 2004
https://doi.org/10.1109/IDEAS.2004.1319808

View Options

Get Access

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

Pipeline rendering: interaction and realism through hardware-based multi-pass rendering

Global illumination models for volume rendering

Precomputed illuminance composition for real-time global illumination