Skip to main content

Sampling hidden objects using nearest-neighbor oracles

Publication ,  Journal Article
Dalvi, N; Kumar, R; Machanavajjhala, A; Rastogi, V
Published in: Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
January 1, 2011

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. Copyright 2011 ACM.

Duke Scholars

Published In

Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

DOI

Publication Date

January 1, 2011

Start / End Page

1325 / 1333
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Dalvi, N., Kumar, R., Machanavajjhala, A., & Rastogi, V. (2011). Sampling hidden objects using nearest-neighbor oracles. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 1325–1333. https://doi.org/10.1145/2020408.2020606
Dalvi, N., R. Kumar, A. Machanavajjhala, and V. Rastogi. “Sampling hidden objects using nearest-neighbor oracles.” Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, January 1, 2011, 1325–33. https://doi.org/10.1145/2020408.2020606.
Dalvi N, Kumar R, Machanavajjhala A, Rastogi V. Sampling hidden objects using nearest-neighbor oracles. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2011 Jan 1;1325–33.
Dalvi, N., et al. “Sampling hidden objects using nearest-neighbor oracles.” Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Jan. 2011, pp. 1325–33. Scopus, doi:10.1145/2020408.2020606.
Dalvi N, Kumar R, Machanavajjhala A, Rastogi V. Sampling hidden objects using nearest-neighbor oracles. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2011 Jan 1;1325–1333.

Published In

Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

DOI

Publication Date

January 1, 2011

Start / End Page

1325 / 1333