- Houle paper on indexing in metric spaces without triangle
inequality; compare with sa-tree and related methods.
- Indyk papers and techniques for high dimensional approximate
nearest neighbor searching. The goal here is to explain the
methods and show how they might be used for incremental nearest
neighbor searching.
- Lars Arge SIGMOD 2004 on priority R-tree
- Reverse Nearest Neighbor and distance semijoin methods
- P2P indexing and analyze/compare Chord and CAN methods (in
particular, see how they are related and how they can be used for
quadtrees)
- BoostMap methods - Athitsos/Sclaroff. The goal here is to explain
the BoostMap method and show how the presented method is related
to FastMap, Lipshcitz embeddings, MetricMap, etc. Also, discuss
contractiveness.
- Skyline queries. Discuss various papers on the subject and
relationship to top k methods. Also, show relationship to
incremental nearest neighbor algorithm of Hjaltason and Samet.
- Computing nearest neighbors in a network where the distances are
constrained by the lengths of paths. Can you apply the
incremental nearest neighbor method of Hjaltason and Samet in such
an environment?
- MaxNearestDist evaluation and clustering. Want to see under what
kind of data distributions and clusters will a MaxNearestDist
estimate be useful and to what extent.
- AESA Method of indexing using distance matrices. How to make an
incremental nearest neighbor algorithm. Some clues and
suggestions in the Hjaltason/Samet tehcnical report
- Evaluate dimension reduction such as that described by Chakrabarti
and Mehrotra.
- INN and range searching in metric space using Methods based on
bidistance functions (RNG, etc.)
- HarPeled and Arya/Malamatos/Mount papers. These papers deal with
methods of indexing Voronoi diagrams. The goal here is to see
whether such methods can be applied to triangulations and
relationship to more traditional quadtree methods.
- Look at learning literature on NN
- Incremental nearest neighbor computation with Hausdorff distances
- Spatial join methods and dynamic plane-sweep (Edwin Jacox will lecture)
- Houle paper on indexing in metric spaces without triangle inequality; compare with sa-tree and related methods.
@inproceedings{Houl05,
folder = {HOULE?},
author = {M. E. Houle and J. Sakuma},
title = "Fast approximate similarity search in
exteremly high-dimensional data sets",
publication = icde05,
note = {to appear},
keywords = {[metric spaces; search tree;
approximate nearest neighbor searching]},
abstract = {No need to be in a metric space and
thus triangle inequality is not needed.}
}
@Article{Nava02,
folder = {BURKHARD/KELLER/METRIC},
author = {G. Navarro},
journal = "{VLDB} Journal",
title = {Searching in metric spaces by spatial approximation},
year = 2002,
volume = 11,
number = 1,
pages = {28--46},
keywords = {[sa-tree; metric spaces]}
}
- Indyk papers and techniques for high dimensional approximate
nearest neighbor searching. The goal here is to explain the
methods and show how they might be used for incremental nearest
neighbor searching.
@inproceedings{Indy98,
author = {P. Indyk and R. Motwani},
title = {Approximate nearest neighbors:
Towards removing the curse of dimensionality},
booktitle = "Proceedings of the 30th Annual
{ACM} Symposium on the Theory of Computing",
address = {Dallas},
month = may,
year = 1998,
pages = {604--613},
keywords = {[points; approximate nearest neighbor;
high-dimensional space]}
}
@InProceedings{Gion99,
folder = {ARYA?},
author = {A. Gionis and P. Indyk and R. Motwani},
title = {Similarity Search in High Dimensions via Hashing},
booktitle = "Proceedings of the 25th International
Conference on Very Large Data Bases ({VLDB})",
editor = {M. P. Atkinson and M. E. Orlowska and
P. Valduriez and S. B. Zdonik and M. L. Brodie},
address = {Edinburgh, Scotland},
year = 1999,
month = sep,
pages = {518--529},
keywords = {[points; similarity searching; approximate nearest
neighbor searching]}
}
- Lars Arge SIGMOD 2004 on priority R-tree
@InProceedings{Arge04,
folder = "ARGE?",
author = {L. Arge and M. de Berg and H. J. Haverkort and K. YiG},
title = {The priority {R}-tree: a practically efficient and worst-case optimal {R}-tree},
booktitle = "Proceedings of the {ACM SIGMOD} Conference",
year = 2004,
address = {Paris, France},
month = jun,
pages = {347--358},
abstract = {},
keywords = {[R-tree]}
}
- Reverse Nearest Neighbor and distance semijoin methods
@InProceedings{Stan00,
folder = {KORN/RNN?},
author = {I. Stanoi and D. Agrawal and A. {El Abbadi}},
title = {Reverse nearest neighbor queries for dynamic databases},
booktitle = {Proceedings {ACM} {SIGMOD} Workshop on Research Issues in Data Mining and Knowledge Discovery},
editor = {D. Gunopulos and R. Rastogi},
address = {Dallas},
year = 2000,
month = may,
pages = {44--53},
keywords = {[distance join; reverse nearest neighbor queries]}
}
@InProceedings{Yang01,
folder = {HJALTASON/DISTANCE SEMI-JOIN},
author = {C. Yang and K.-I. Lin},
title = {An index structure for efficient reverse nearest neighbor queries},
booktitle = "Proceedings of the 17th {IEEE} International Conference on Data Engineering",
year = 2001,
address = {Heidelberg, Germany},
month = apr,
pages = {485--492},
keywords = {[points; reverse nearest neighbor; distance semi-join]}
}
@InProceedings{Korn00,
folder = {KORN/RNN },
author = {F. Korn and S. Muthukrishnan},
title = {Influence sets based on reverse nearest neighbor queries},
booktitle = "Proceedings of the {ACM SIGMOD} Conference",
editor = {W. Chen and J. Naughton and P. A. Bernstein},
year = 2000,
address = {Dallas},
month = may,
pages = {201--212},
keywords = {[distance join; reverse nearest neighbor queries]}
}
@InProceedings{Hjal98,
folder = "HJALTASON",
author = {G. R. Hjaltason and H. Samet},
title = {Incremental distance join algorithms for spatial databases},
booktitle = "Proceedings of the {ACM SIGMOD} Conference",
editor = {L. Hass and A. Tiwary},
year = 1998,
address = {Seattle, WA},
month = jun,
pages = {237--248},
abstract = {Two new spatial join operations, distance join and distance
semi-join, are introduced where the join output is ordered
by the distance between the spatial attribute values of the
joined tuples. Incremental algorithms are presented for
computing these operations, which can be used in a
pipelined fashion, thereby obviating the need to wait for
their completing when only a few tuples are needed.},
keywords = {[spatial join; incremental nearest neighbor;
incremental algorithms; distance join]}
}
@InProceedings{Shin00,
folder = {HJALTASON/DISTANCE SEMI-JOIN},
author = {H. Shin and B. Moon and S. Lee},
title = {Adaptive Multi-Stage Distance Join Processing},
booktitle = "Proceedings of the {ACM SIGMOD} Conference",
editor = {W. Chen and J. Naughton and P. A. Bernstein},
year = 2000,
address = {Dallas},
month = may,
pages = {343--354},
keywords = {[distance join]}
}
- P2P indexing and analyze/compare Chord and CAN methods (in
particular, see how they are related and how they can be used for
quadtrees)
@InProceedings{Ratn01,
folder = {KARP},
author = {S. Ratnasamy and P. Francis and M. Handley and
R. Karp},
title = {A scalable content-addressable network},
booktitle = {Proceedings of the {ACM SIGCOMM} Conference},
address = {San Diego},
month = aug,
year = 2001,
pages = {161--172},
keywords = {content-addressable; peer-to-peer lookup service}
}
@InProceedings{Stoi01,
folder = {KARP?},
author = {I. Stoica and R. Morris and D. R. Karger and
M. F. Kaashoek an
d H. Balakrishnan},
title = {Chord: A scalable peer-to-peer lookup service for
internet app
lications},
booktitle = {Proceedings of the {ACM SIGCOMM} Conference},
address = {San Diego},
month = aug,
year = 2001,
pages = {149--160},
keywords = {content-addressable; peer-to-peer lookup service}
}
@inproceedings{Tani04,
folder = {TANIN},
author = {E. Tanin and A. Harwood and H. Samet},
title = "Indexing distributed complex data for complex queries",
pages = {81--90},
publication = dg04,
keywords = {[peer-to-peer indexing; distributed hashing; regions; rectangles; chord method]}
}
- BoostMap methods - Athitsos/Sclaroff. The goal here is to explain
the BoostMap method and show how the presented method is related
to FastMap, Lipshcitz embeddings, MetricMap, etc. Also, discuss
contractiveness.
@InProceedings{Athi04,
folder = {SCLAROFF?},
author = {V. Athitsos and J. Alon and S. Sclaroff and G. Kollios},
title = {BoostMap: a method for efficient approximate similarity rankings},
booktitle = {Proceedings of Computer Vision and Pattern Recognition'04},
address = {Washington, DC},
month = jun,
year = 2004,
page = {268--275},
keywords = {[metric space embedding; BoostMap; FastMap]}
}}
- Skyline queries. Discuss various papers on the subject and
relationship to top k methods. Also, show relationship to
incremental nearest neighbor algorithm of Hjaltason and Samet.
@InProceedings{Papa03,
folder = {PAPADIAS/SKYLINE?},
author = {D. Papadias and Y. Tao and G. Fu and B. Seeger},
title = {An optimal and progressive algorithm for skyline queries},
booktitle = "Proceedings of the {ACM SIGMOD} Conference",
year = 2003,
address = {San Diego},
month = jun,
pages = {467--478},
abstract = {},
keywords = {[points; skyline queries; nearest neighbor finding]}
}
- Computing nearest neighbors in a network where the distances are
constrained by the lengths of paths. Can you apply the
incremental nearest neighbor method of Hjaltason and Samet in such
an environment?
@InProceedings{Kola04,
folder = {SHAHABI?},
author = {M. R. K. and C. Shahabi},
title = {Voronoi-based k nearest neighbor search for spatial network databases},
booktitle = "Proceedings of the 30th International Conference on Very Large Data Bases ({VLDB})",
editor = {M. A. Nascimento and M. T. {\"O}zsu and D. Kossman and R. J. Miller and J. A. Blakely and K. B. Schiefer},
address = {Toronto, Canada},
year = 2004,
month = sep,
pages = {840--851},
keywords = {[networks; lines; points; nearest neighbor searching]},
abstract = {Finding nearest neighbors where the metric is distance along
a network rather than as the crow flies.}
}
- MaxNearestDist evaluation and clustering. Want to see under what
kind of data distributions and clusters will a MaxNearestDist
estimate be useful and to what extent.
@InProceedings{Same03c,
folder = {SAMET},
author = {H. Samet},
title = {Depth-first $k$-nearest neighbor finding using the {MaxNearestDist} estimator},
booktitle = "Proceedings of the 12th International Conference on Image Analysis and Processing",
year = 2003,
address = {Mantova, Italy},
month = sep,
pages = {486--491},
keywords = {[points; nearest neighbor; depth-first; branch and bound]}
}
@InProceedings{Ferh01b,
folder = "GUTTMAN / R-TREES?",
author = {H. Ferhatosmanoglu and I. Stanoi and D. Agrawal and A. {El Abbadi}},
title = {Constrained nearest neighbor queries},
booktitle = "Advances in Spatial and Temporal Databases --- 7th International Symposium, {SSTD}'01",
editor = {C. S. Jensen and M. Schneider and B. Seeger and V. J. Tsotras},
year = 2001,
address = {Redondo Beach, CA},
month = jul,
macronote = lncs2121,
pages = {257--278},
keywords = {[points; constrained nearest neighbor searching; maxnearestdist; minmaxdist]}
}
- AESA Method of indexing using distance matrices. How to make an
incremental nearest neighbor algorithm. Some clues and
suggestions in the Hjaltason/Samet tehcnical report
@article{Vida86,
folder = "BURKHARD/KELLER/METRIC",
author = {E. {Vidal Ruiz}},
title = "An algorithm for finding nearest neighbours in (approximately)
constant average time",
journal = prl,
volume = 4,
number = 3,
year = 1986,
month = jul,
pages = {145--157},
abstract = {A new algorithm is proposed which finds the Nearest Neighbor
of a given sample in approximately constant average time
complexity /(i.e. independent of the data set size/) called
AESA.},
keywords = {[metric spaces; nearest neighbor; distance matrix; AESA]}
}
@Article{Mico94,
folder = {BURKHARD/KELLER/METRIC},
author = {L. Mic\'{o} and J. Oncina and E. Vidal},
title = {A new version of the nearest-neighbour approximating and
eliminating search algorithm ({AESA}) with linear
preprocessing-time and memory requirements},
journal = "Pattern Recognition Letters",
year = 1994,
volume = 15,
number = 1,
month = jan,
pages = {9--17},
keywords = {[metric spaces; nearest neighbor]},
abstract = {In this paper a new version of the AESA is introduced which
only requires linear preprocessing time and memory. The
performance of the new version, referred to as `Linear
AESA' (LAESA), is studied through a number of simulation
experiments in abstract metric spaces.}
}
@inproceedings{Wang90a,
folder = "BURKHARD/KELLER/METRIC",
author = "T. L. Wang and D. Shasha",
title = "Query processing for distance metrics",
booktitle = {Proceedings of the 16th International Conference on Very Large Databases ({VLDB})},
editor = {D. McLeod and R. Sacks-Davis and H.-J. Schek},
address = {Brisbane, Australia},
year = 1990,
month = aug,
pages = "602--613",
abstract = "In applications such as vision and molecular
biology, a common problem is to find the similar
objects to a given target (according to some
distance measure) in a large database. This paper
presents a scheme for query processing in such
situations.",
keywords = "[metric spaces; distance; pattern matching]"
}
@techreport{Hjal00b,
folder = {HJALTASON },
author = {G. R. Hjaltason and H. Samet},
title = {Incremental similarity search in multimedia databases},
institution = {University of Maryland},
address = "College Park, MD",
number = {TR-4199},
type = {Computer Science Department},
month = nov,
year = 2000,
abstract = {},
keywords = {[points; high\hyp{}dimensional data; similarity searching;
incremental nearest neighbor]}
}
- Evaluate dimension reduction such as that described by Chakrabarti
and Mehrotra.
@InProceedings{Chak00b,
folder = {MEHROTRA},
author = {K. Chakrabarti and S. Mehrotra},
title = {Local dimensionality reduction: a new approach to indexing high\hyp{}dimensional spaces},
booktitle = "Proceedings of the 26th International Conference on Very Large Data Bases ({VLDB})",
editor = {A. {El Abbadi} and M. L. Brodie and S. Chakravarthy and U. Dayal and N. Kamel and G. Schlageter and K.-Y. Whang},
address = {Cairo, Egypt},
year = 2000,
month = sep,
pages = {89--100},
keywords = {[points; high\hyp{}dimensional data;
nearest neighbor searching; dimension reduction]}
}
- INN and range searching in metric space using Methods based on
bidistance functions (RNG, etc.)
@article{Jaro92,
folder = "TOUSSAINT",
key = "[Jaro92]",
author = "J. W. Jaromczyk and G. T. Toussaint",
title = "Relative neighborhood graphs and their relatives",
journal = "Proceedings of the IEEE",
volume = 80,
number = 9,
pages = "1502--1517",
month = sep,
year = 1992,
abstract = "Describes interrelationships between a number of structures
such as the relative neighborhood graph, Delaunay triangulation,
Gabriel graph, and the minimum spanning tree.",
keywords = "[points; relative neighborhood graphs; Delaunay graphs; Gabriel graphs; Delaunay triangulations; minimum spanning trees]"
}
- HarPeled and Arya/Malamatos/Mount papers. These papers deal with
methods of indexing Voronoi diagrams. The goal here is to see
whether such methods can be applied to triangulations and
relationship to more traditional quadtree methods.
@InProceedings{Arya02a,
folder = {MOUNT?},
author = {S. Arya and T. Malamatos},
title = {Linear-size approximate voronoi diagrams},
booktitle = "Proceedings of the 13th Annual {ACM-SIAM} Symposium on Discrete Algorithms",
year = 2002,
address = {Las Vegaa, NV},
month = jan,
pages = {147--155},
keywords = {[regions; triangulations; Voronoi diagram; approximate Voronoi diagram]},
abstract = {}
}
@InProceedings{Arya02b,
folder = {MOUNT?},
author = {S. Arya and T. Malamatos and D. M. Mount},
title = {Space-efficient approximate Voronoi diagrams},
booktitle = "Proceedings of the 33rd Annual {ACM} Symposium on the Theory of Computing",
address = {Montr\'{e}al, Que\'{e}bec, Canada},
month = jan,
year = 2002,
pages = {721--730},
keywords = {[regions; triangulations; Voronoi diagram; approximate Voronoi diagram]},
abstract = {}
}
@InProceedings{HarP01c,
folder = {},
author = {S. {Har-Peled}},
title = {A replacement for {Voronoi} diagrams of near linear size},
booktitle = "Proceedings of the 42nd {IEEE} Annual Symposium on Foundations of Computer Science",
year = 2001,
address = {Las Vegas, NV},
month = oct,
pages = {94--103},
keywords = {[regions; triangulations; Voronoi diagram; approximate Voronoi diagram]}
}
- Look at learning literature on NN
- Incremental nearest neighbor computation with Hausdorff distances
- Spatial join methods and dynamic plane-sweep (Edwin Jacox will lecture)
|