Queries about the largest empty rectangle in large 2-dimensional datasets stored in secondary memory
Sea S un conjunto de puntos ubicado en un rectǹgulo R, y q un punto que no est ̀en S.- Este artc̕ulo describe el diseǫ, la implementacin̤ y experimentacin̤ de diferentes algoritmos para resolver los siguientes problemas: (i) MER, que consiste en encontrar un rectǹgulo vaco̕ de mx̀ima r̀ea conteni...
Kaydedildi:
| Diğer Yazarlar: | , , , , |
|---|---|
| Materyal Türü: | Kitap |
| Dil: | English |
| Konular: | |
| Online Erişim: | Queries about the largest empty rectangle in large 2-dimensional datasets stored in secondary memory |
| Etiketler: |
Etiketle
Etiket eklenmemiş, İlk siz ekleyin!
|
| Özet: | Sea S un conjunto de puntos ubicado en un rectǹgulo R, y q un punto que no est ̀en S.- Este artc̕ulo describe el diseǫ, la implementacin̤ y experimentacin̤ de diferentes algoritmos para resolver los siguientes problemas: (i) MER, que consiste en encontrar un rectǹgulo vaco̕ de mx̀ima r̀ea contenido en R y que no contiene un punto de S, y (ii) QMER, que consiste en encontrar un rectǹgulo con las mismas restricciones dadas para el problema MER y que, adems̀, debe contener a q. En ambos problemas se asume que no existe suficiente memoria para almacenar todos los objetos del conjunto S. De acuerdo con la literatura, ambos problemas son de mucha utilidad prc̀tica, en m̀bitos como la minera̕ de datos, sistemas de informacin̤ geogrf̀ica, por nombrar algunos. Concretamente, en este trabajo se proponen dos algoritmos que asumen que S se encuentra almacenado en memoria secundaria y que no es posible almacenarlo completamente en memoria. El primero resuelve el problema QMER y consiste en disminuir el tamaǫ de mediante la utilizacin̤ de zonas de dominancia y luego, mediante un algoritmo propuesto por Orlowski (1990), se procesan los puntos no descartados. El segundo, a su vez, resuelve el problema MER y consiste en dividir R en cuatro subrectǹgulos generando cuatro subconjuntos de similar tamaǫ los que se procesan mediante un algoritmo propuesto en Edmonds et al. (2003), combinando finalmente las soluciones parciales para obtener la solucin̤ global. Con el objeto de verificar la eficiencia de los algoritmos, se muestran los resultados de una serie de experimentos considerando datos sintťicos y reales. |
|---|---|
| ISBN: | 0120-5609 (versin̤ impresa) ; 2248-8723 (versin̤ online) |