2011 SamplingHiddenObjectsUsingNeare

• (Dalvi et al., 2011) ⇒ Nilesh Dalvi, Ravi Kumar, Ashwin Machanavajjhala, and Vibhor Rastogi. (2011). “Sampling Hidden Objects Using Nearest-neighbor Oracles.” In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2011) Journal. ISBN:978-1-4503-0813-7 doi:10.1145/2020408.2020606

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222011%22+Sampling+Hidden+Objects+Using+Nearest-neighbor+Oracles
• http://dl.acm.org/citation.cfm?id=2020408.2020606&preflayout=flat#citedby

Quotes

Author Keywords

• Algorithms; experimentation; information search and retrieval; nearest-neighbors; performance; sampling; size estimation; theory; voronoi cell

Abstract

Given an unknown set of objects embedded in the Euclidean plane and a nearest-neighbor oracle, how to estimate the set size and other properties of the objects? In this paper we address this problem. We propose an efficient method that uses the Voronoi partitioning of the space by the objects and a nearest-neighbor oracle. Our method can be used in the hidden web / databases context where the goal is to estimate the number of certain objects of interest. Here, we assume that each object has a geographic location and the nearest-neighbor oracle can be realized by applications such as maps, local, or store-locator APIs. We illustrate the performance of our method on several real-world datasets.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2011 SamplingHiddenObjectsUsingNeare	Ravi Kumar Ashwin Machanavajjhala Vibhor Rastogi Nilesh Dalvi			Sampling Hidden Objects Using Nearest-neighbor Oracles				10.1145/2020408.2020606		2011