NDLI: Dynamic spatial approximation trees

Please wait, while we are loading the content...

Experimental average-case performance evaluation of online algorithms for routing and wavelength assignment and throughput maximization in WDM optical networks

An experimental study of sorting and branch prediction

Terracost: Computing least-cost-path surfaces for massive grid terrains

A graph approach to the threshold all-against-all substring matching problem

A dictionary implementation based on dynamic perfect hashing

Preface

Engineering a cache-oblivious sorting algorithm

Sum-of-squares heuristics for bin packing and memory allocation

Efficient models for timetable information in public transportation systems

Faster placement of hydrogens in protein structures by dynamic programming

Papers from ALENEX 2005

On the adaptiveness of Quicksort

An experimental study of different approaches to solve the market equilibrium problem

Better external memory suffix array construction

Approximating the true evolutionary distance between two genomes

Dynamic spatial approximation trees

Content Provider	ACM Digital Library
Author	Navarro, Gonzalo Reyes, Nora
Copyright Year	2008
Abstract	Metric space searching is an emerging technique to address the problem of efficient similarity searching in many applications, including multimedia databases and other repositories handling complex objects. Although promising, the metric space approach is still immature in several aspects that are well established in traditional databases. In particular, most indexing schemes are static, that is, few of them tolerate insertion or deletion of elements at reasonable cost over an existing index. The spatial approximation tree $(\textit{sa--tree})$ has been experimentally shown to provide a good tradeoff between construction cost, search cost, and space requirement. However, the $\textit{sa--tree}$ is static, which renders it unsuitable for many database applications. In this paper, we study different methods to handle insertions and deletions on the $\textit{sa--tree}$ at low cost. In many cases, the dynamic construction (by successive insertions) is even faster than the previous static construction, and both are similar elsewhere. In addition, the dynamic version significantly improves the search performance of $\textit{sa--trees}$ in virtually all cases. The result is a much more practical data structure that can be useful in a wide range of database applications.
Starting Page	1
Ending Page	68
Page Count	68
File Format	PDF
ISSN	10846654
e-ISSN	10846654
DOI	10.1145/1227161.1322337
Journal	Journal of Experimental Algorithmics (JEA)
Volume Number	12
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-06-12
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Multimedia databases Similarity or proximity search Spatial and multidimensional search Spatial approximation tree
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Speeding up spatial approximation search in metric spaces

Multidimensional Height-Balanced Trees

Effective and Efficient Algorithms for Flexible Aggregate Similarity Search in High Dimensional Spaces

Multidimensional balanced binary trees

On the Height of Multidimensional Height-Balanced Trees

Parallel construction of multidimensional binary search trees

Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases

Region proximity in metric spaces and its use for approximate similarity search

Keyword proximity search in XML trees

Dynamic spatial approximation trees

Similar Documents

Speeding up spatial approximation search in metric spaces

Multidimensional Height-Balanced Trees

Effective and Efficient Algorithms for Flexible Aggregate Similarity Search in High Dimensional Spaces

Multidimensional balanced binary trees

On the Height of Multidimensional Height-Balanced Trees

Parallel construction of multidimensional binary search trees

Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases

Region proximity in metric spaces and its use for approximate similarity search

Keyword proximity search in XML trees

Dynamic spatial approximation trees