Cumincad : CUMINCAD Papers : Search Results

CumInCAD is a Cumulative Index about publications in Computer Aided Architectural Design
supported by the sibling associations ACADIA, CAADRIA, eCAADe, SIGraDi, ASCAAD and CAAD futures

PDF papers
References

Hits 1 to 20 of 2476

Reformat results as: short short into frame detailed detailed into frame

_id	8d2b
id	8d2b
authors	Cross, N. and Maver, T.W.
year	1973
title	Computer Aids for Design Participation
source	Architectural Design, vol XL 111, 5, 274
series	journal paper
email
last changed	2003/09/06 08:41

_id	ga0024
id	ga0024
authors	Ferrara, Paolo and Foglia, Gabriele
year	2000
title	TEAnO or the computer assisted generation of manufactured aesthetic goods seen as a constrained flux of technological unconsciousness
source	International Conference on Generative Art
summary	TEAnO (Telematica, Elettronica, Analisi nell'Opificio) was born in Florence, in 1991, at the age of 8, being the direct consequence of years of attempts by a group of computer science professionals to use the digital computers technology to find a sustainable match among creation, generation (or re-creation) and recreation, the three basic keywords underlying the concept of “Littérature potentielle” deployed by Oulipo in France and Oplepo in Italy (see “La Littérature potentielle (Créations Re-créations Récréations) published in France by Gallimard in 1973). During the last decade, TEAnO has been involving in the generation of “artistic goods” in aesthetic domains such as literature, music, theatre and painting. In all those artefacts in the computer plays a twofold role: it is often a tool to generate the good (e.g. an editor to compose palindrome sonnets of to generate antonymic music) and, sometimes it is the medium that makes the fruition of the good possible (e.g. the generator of passages of definition literature). In that sense such artefacts can actually be considered as “manufactured” goods. A great part of such creation and re-creation work has been based upon a rather small number of generation constraints borrowed from Oulipo, deeply stressed by the use of the digital computer massive combinatory power: S+n, edge extraction, phonetic manipulation, re-writing of well known masterpieces, random generation of plots, etc. Regardless this apparently simple underlying generation mechanisms, the systematic use of computer based tools, as weel the analysis of the produced results, has been the way to highlight two findings which can significantly affect the practice of computer based generation of aesthetic goods: ? the deep structure of an aesthetic work persists even through the more “desctructive” manipulations, (such as the antonymic transformation of the melody and lyrics of a music work) and become evident as a sort of profound, earliest and distinctive constraint; ? the intensive flux of computer generated “raw” material seems to confirm and to bring to our attention the existence of what Walter Benjamin indicated as the different way in which the nature talk to a camera and to our eye, and Franco Vaccari called “technological unconsciousness”. Essential references R. Campagnoli, Y. Hersant, “Oulipo La letteratura potenziale (Creazioni Ri-creazioni Ricreazioni)”, 1985 R. Campagnoli “Oupiliana”, 1995 TEAnO, “Quaderno n. 2 Antologia di letteratura potenziale”, 1996 W. Benjiamin, “Das Kunstwerk im Zeitalter seiner technischen Reprodizierbarkeit”, 1936 F. Vaccari, “Fotografia e inconscio tecnologico”, 1994
series	other
more	http://www.generativeart.com/
last changed	2003/08/07 17:25

_id	ecaade2013_057
id	ecaade2013_057
authors	Orbey, Betül and Gürel, Nihan
year	2013
title	Digital Design Tools versus Architectural Representation and Design Approach
doi	https://doi.org/10.52842/conf.ecaade.2013.2.415
source	Stouffs, Rudi and Sariyildiz, Sevil (eds.), Computation and Performance – Proceedings of the 31st eCAADe Conference – Volume 2, Faculty of Architecture, Delft University of Technology, Delft, The Netherlands, 18-20 September 2013, pp. 415-423
summary	This study aims to investigate the relation between evolving graphic representations and due to new digital tools and how they affect architects’ approach to design process. In order to do this, Yap_ Magazine being published since 1973 in Turkey will be retrieved and data related to types of architectural design representation used will be recorded. The study will conclude with an evaluation of new representation means such as 3D render, other 3D digital products and diagrams and how they have influenced new approach to design.
wos	WOS:000340643600042
keywords	Digital design tool; architectural representation, architectural design thinking.
series	eCAADe
email
last changed	2022/06/07 08:00

_id	sigradi2023_463
id	sigradi2023_463
authors	Acuna, Tomás, Avendano, Martín, García-Alvarado, Rodrigo, Banda, Pablo and Soza, Pedro
year	2023
title	Parametric design of multipurpose 3d-printed walls based on Roberto Matta´s drawings
source	García Amen, F, Goni Fitipaldo, A L and Armagno Gentile, Á (eds.), Accelerated Landscapes - Proceedings of the XXVII International Conference of the Ibero-American Society of Digital Graphics (SIGraDi 2023), Punta del Este, Maldonado, Uruguay, 29 November - 1 December 2023, pp. 483–494
summary	A research and workflow are presented for the parametric design and 3D printing of multipurpose walls, based on illustrations of residential environments made by the Chilean surrealist painter Roberto Matta. These drawings present walls with different shapes and associated uses that expand the housing experiences and suggest relaxed and suggestive spaces. The work analyzes the formal variations and different types of elements that can be included in the design of walls, as well as different textures and ribs that can be incorporated into the walls for their appearance and structural integrity. Possibilities are reviewed for the efficient design and execution of complex shapes using parametric procedures for 3D printing. Determining a generative capacity with high functional and expressive versatility, and construction feasibility.
keywords	Parametric Design, 3d-printing, Wall, Surrealism, Roberto Matta
series	SIGraDi
email
last changed	2024/03/08 14:07

_id	c39a
authors	Ahumada Gallardo, N., López Morales, B., Mora Olate, M.L. and Muñoz, V.C.
year	2001
title	MARCO ANTONIO DE LA PARRA COMO NARRADOR Y ENSAYISTA. MONOGRAFIA MULTIMEDIAL (Marco Antonio de la Parra as Narrator and Writer. Monography in Multimedia)
source	SIGraDi biobio2001 - [Proceedings of the 5th Iberoamerican Congress of Digital Graphics / ISBN 956-7813-12-4] Concepcion (Chile) 21-23 november 2001, pp. 268-270
summary	The analysis of Marco Antonio de la Parra’s novels and essays from the discourse perspective, is the contents of an interdisciplinary work for modernizing and improving communicative possibilities of universitary thesis through multimedia. For the multimedia design, the main and most recent digital creating software for the graphic treatment of texts and images were analised, then the navigation system and screens were designed, difining backgrounds, texts, audio and video, besides buttons and hits. Results permit: 1. To present the contents in an easy access and transportation support, reducing production costs. 2. The offering of three communication supports: written text, audio and video. 3. Ostensibly improves universitary thesis and seminars quality.
series	SIGRADI
email
last changed	2016/03/10 09:47

_id	sigradi2017_072
id	sigradi2017_072
authors	Amaral de Andrade, Bruno; Camila Marques Zyngier, Camila Marques Zyngier, Ana Clara Mourão Moura
year	2017
title	Roteiro Metodológico para Gamificação do Geodesign Aplicado ao Planejamento Urbano: Por uma Experiência Lúdica no Projeto de Futuros Alternativos para a Cidade com Crianças [Methodological Guide for the Gamification of Geodesign Applied to Urban Planning: For a Ludic Experience on the Project of Alternative Futures for the City with Children]
source	SIGraDi 2017 [Proceedings of the 21th Conference of the Iberoamerican Society of Digital Graphics - ISBN: 978-956-227-439-5] Chile, Concepción 22 - 24 November 2017, pp.491-495
summary	This article aims to present a Methodological Guide to add gamification elements to the Geodesign framework when planning the future of the city, using Geogames such Minecraft, with the participation of children in Tirol, in Brazil. The problematic tackled is related to the challenges that participants of a Geodesign workshop face when co-designing projects as alternative futures for the territory, such as losing engagement and involvement. To support the participants overcome these challenges we incorporate playfulness into the some of the Geodesign workshop phases enhancing geovisualization, collaboration and cognition.
keywords	Geodesign; Geogames; Geovisualization; Participatory Planning; Chindren’s Design.
series	SIGRADI
email
last changed	2021/03/28 19:58

_id	f1bf
authors	Amorim, S.L., Soares Madeira Domingues, L.C., Pereira Nunes, R. and De Almeida Peixoto, L.
year	2000
title	Centro de Referência e Informação em Habitação - Infohab (Reference Center and Information on Housing - Infohab)
source	SIGraDi’2000 - Construindo (n)o espacio digital (constructing the digital Space) [4th SIGRADI Conference Proceedings / ISBN 85-88027-02-X] Rio de Janeiro (Brazil) 25-28 september 2000, pp. 55-57
summary	The Center of Reference and Information in Habitation - INFOHAB - is a project led for the ANTAC, that intends to facilitate the access to the technique information relative to all the aspects and subjects that are contained in the construction environment concept, through the captation, selection, organization and spreading this information, offering it in the Internet through a database permanently brought up to date with the reference and, always when authorized, with the complete works. The objective of this article is to present the project and to reflect on the possibilities offered for the Internet as a tool to fulfill some of its objectives, established in the broadcasting of the information and the technology and that they search to corroborate with the creation of the basic conditions to reach upper standards of quality in the information, the products and the jobs offered in the area of the civil construction, architecture and urbanism, considering the characterizes of this thematic area.
series	SIGRADI
email
last changed	2016/03/10 09:47

_id	acadia23_v2_520
id	acadia23_v2_520
authors	Ampanavos, Spyridon; Bernal, Marcelo; Okhoya, Victor
year	2023
title	Daylight ML: A General-Purpose Deep-Learning Surrogate Model for Annual Daylight Distribution
source	ACADIA 2023: Habits of the Anthropocene: Scarcity and Abundance in a Post-Material Economy [Volume 2: Proceedings of the 43rd Annual Conference for the Association for Computer Aided Design in Architecture (ACADIA) ISBN 979-8-9891764-0-3]. Denver. 26-28 October 2023. edited by A. Crawford, N. Diniz, R. Beckett, J. Vanucchi, M. Swackhamer 520-531.
summary	Building performance simulation, such as daylight evaluation can lead to better quality designs. However, time constraints are currently limiting its use for design exploration. Surrogate modeling can offer drastic speed improvements to simulation processes, but existing models are either project specific or offer limited flexibility to design inputs, while requiring a significant initial investment for their training. This research introduces a method for predicting spatial distribution of annual daylight metrics using a raytrac- ing-based encoding of the inputs, and a deep-learning surrogate model. The method can operate on spaces of any shape. Using synthetic data, surrogate models for Atlanta, Georgia, and Boston, Massachusetts, were trained, and achieved low average errors on the test set for all daylight metrics considered. Furthermore, models trained on simple datasets of rectangular spaces were able to predict accurate results for L-shaped, circular, and courtyard-shaped spaces, and for sensors that had twice the density of the ones in the training set. Overall, the results suggest that trained models can be used to evaluate the daylight quality of any project or design within their respective locations.
series	ACADIA
type	paper
email
last changed	2024/12/20 09:13

_id	269b
id	269b
authors	Andrea Carnicero, Gustavo Fornari & Carlos Pereyra
year	2004
title	ARQUITECTURA, CINE Y LITERATURA: LA SEDUCCIÓN DE LA GEOMETRÍA
source	Proceedings of the Fourth International Conference of Mathematics & Design, Special Edition of the Journal of Mathematics & Design, Volume 4, No.1, pp. 27-34.
summary	¿Estamos presenciando un nuevo paradigma hacia otra forma de concebir la matemática?. El presente ensayo pretende indagar, a través del análisis y discusiones sobre diferentes obras literarias, cinematográficas y proyectos arquitectónicos, clásicos y contemporáneos, la relación entre la arquitectura y la literatura a partir de las estructuras matemáticas que los sustentan y cómo estas se han modificado o evolucionado a partir de los cambios tecnológicos de las últimas décadas. Relacionaremos la literatura y la arquitectura contemporánea pos revolución digital, con sus propiedades de nolinealidad y de fragmentación. Nuestra línea de investigación se centra en cuáles pueden ser las aportaciones esencialmente nuevas de la cultura digital a la producción de la arquitectura y la literatura, partiendo de su base estructural. La era informática trae con ella implicaciones que desestabilizan los conceptos tradicionales de espacio y tiempo. Nos preguntamos cuáles son los cambios en las estructuras textuales a partir de la era digital, cuáles son las nuevas estructuras geométricas, cómo influyen estas nuevas geometrías en la arquitectura, en el cine y en la literatura, en esta era de la información y qué rol ocupa la matemática en este cambio. El desarrollo de las ciencias contemporánea ha generado teorías que transforman nuestro conocimiento del universo. Caos, Teoría de la complejidad, Fractales son términos que caracterizan estos conceptos. En arquitectura estas teorías han tenido importancia en la producción de arquitectura "no-lineal" por medio de el uso de computadoras, especialmente en trabajos de arquitectos como Frank Gehry, Zevi Hecker, Greg Lynn, ARM y O.C.E.A.N UK, entre otros. En esta época informatizada la relación de la arquitectura con las demás ciencias (como la física y la matemática), con otros códigos como el lenguaje (por ejemplo en la narración) y con los límites del pensamiento filosófico, pueden hallarse hoy, tanto en el repertorio del deconstructivismo, en el repertorio “minimalista”, como en las abstracciones de los jóvenes nacidos con la computadora, que emulan cintas de Moebius, topologías “no euclideanas”, “estructuras líquidas” o ya en el campo de la literatura formas virtuales como en Calvino o dimensiones paralelas, bifurcadas, etc. como en Cortázar o Borges. Sin embargo, podemos preguntarnos si esta proliferación exuberante es el desarrollo de un organismo sólidamente construido, que adquiere cada día más cohesión y unidad en su propio crecimiento o si, por el contrario, no es más que el signo exterior de una tendencia a un fraccionamiento cada vez mayor, debido a la naturaleza misma de las matemáticas y si éstas no se estarán convirtiendo en una torre de Babel de disciplinas autónomas, aisladas unas de otras, tanto en sus principios como en sus métodos e incluso en su lenguaje. En una palabra, hoy, en esta tendencia, ¿estamos presenciando un nuevo paradigma hacia otra forma de concebir la matemática?.
series	other
type	normal paper
email
last changed	2005/04/08 17:14

_id	sigradi2010_209
id	sigradi2010_209
authors	Aroztegui, Carmen
year	2010
title	Superficies adulteradas: el muro en línea y la representación fílmica [Adulterated surfaces: the online wall and conematic representation]
source	SIGraDi 2010_Proceedings of the 14th Congress of the Iberoamerican Society of Digital Graphics, pp. Bogotá, Colombia, November 17-19, 2010, pp. 209-212
summary	Online communities use a “wall” as a place to articulate non - synchronic communication among its members. Such a place, however, poorly explores the metaphor of the wall as a means of enhancing online experiences. Online “walls” do not explore or challenge the richness of a real wall, and they do not embrace new experiences that are only possible in the digital world. In order to tackle these issues, this paper analyzes three movie scenes where the everyday perception of the wall is altered by madness and estrangement. Finally, the paper suggests how these perceptions of the wall could be integrated into interfaces using touch screen technologies.
keywords	online, wall, metaphor, film, representation
series	SIGRADI
email
last changed	2016/03/10 09:47

_id	caadria2021_233
id	caadria2021_233
authors	Ascoli, RaphaÃ«l
year	2021
title	Augmenting computational design agency in emerging economies
doi	https://doi.org/10.52842/conf.caadria.2021.2.639
source	A. Globa, J. van Ameijde, A. Fingrut, N. Kim, T.T.S. Lo (eds.), PROJECTIONS - Proceedings of the 26th CAADRIA Conference - Volume 2, The Chinese University of Hong Kong and Online, Hong Kong, 29 March - 1 April 2021, pp. 639-648
summary	This /practice-based design research/ investigates the possibility of computational design to increase agency and impact in emerging economies through real-world projects. By cultivating a new kind of relationship to issues in development and local untapped resources, they inspire for more public engagement and resource-based conversations within a spatial framework. The topics that were addressed in this research are the democratization of data and affordability of construction. These two on-going early-stage initiatives have used computational design tools at specific areas in the projects development, therefore optimizing the parts where low-tech tools werent sufficient. This demand driven design process explores ways in which different levels of technology can augment each other.
keywords	space; resource; housing; myanmar; optimization
series	CAADRIA
email
last changed	2022/06/07 07:54

_id	8eb4
authors	Athithan, G. and Patnaik, L.M.
year	1987
title	Geometric Searching In Extended CSG Models : Application to Solid Modeling and Viewing
source	February, 1987. 30 p. : ill
summary	In this paper, the CSG representation scheme is augmented with the 'cartesian product.' The sweep method of generating solids is encompassed by this 'Extended CSG' formalism. The point inclusion problem encountered in the area of geometric searching in computational geometry is discussed in the context to solid models represented by 'extended CSG.' A simple algorithm to solve it that has a time complexity O(n), where n is the number of primitives, is presented. Allowing for preprocessing and extra storage, a second efficient algorithm, having a time complexity O(log n), is developed. The relevance of point inclusion problem in solid modelling techniques is indicated. An extended CSG based solid modeling method is proposed. A solution to the problem of hidden line removal, that uses the faster algorithm for the point inclusion problem, is also presented in the paper
keywords	point inclusion, computational geometry, data structures, solid modeling, CSG, computer graphics, hidden lines
series	CADline
last changed	2003/06/02 14:41

_id	sigradi2003_047
id	sigradi2003_047
authors	Baccaglio, S., Brebbia, V. Bueno, R., Lagorio, L., Noya, A., Salgado, M., Rucq, M. and Pons, A.
year	2003
title	Una Herramienta Alternativa Para La Comunicación Académica (An Alternative Tool for the Academic Communication)
source	SIGraDi 2003 - [Proceedings of the 7th Iberoamerican Congress of Digital Graphics] Rosario Argentina 5-7 november 2003
summary	The aim of this report is to develop a digital pattern easy to use, which will be a suitable tool to display images and texts for academic purposes. The proposal is done through the configuration of a html code page. Besides the study proposes to carry out a digital catalog in order to make easy the files and communication of graphic and photographic documentation. The case of some urban transformations in Rosario's riverside sets an example of its use and verifies its potential condition.
series	SIGRADI
email
last changed	2016/03/10 09:47

_id	ecaade2020_076
id	ecaade2020_076
authors	Bai, Nan, Azadi, Shervin, Nourian, Pirouz and Pereira Roders, Ana
year	2020
title	Decision-Making as a Social Choice Game - Gamifying an urban redevelopment process in search for consensus
doi	https://doi.org/10.52842/conf.ecaade.2020.2.555
source	Werner, L and Koering, D (eds.), Anthropologic: Architecture and Fabrication in the cognitive age - Proceedings of the 38th eCAADe Conference - Volume 2, TU Berlin, Berlin, Germany, 16-18 September 2020, pp. 555-564
summary	The paper reports the formulation, the design, and the results of a serious game developed for structuring negotiations concerning the redevelopment of a university campus with various stakeholders. The main aim of this research was to formulate the redevelopment planning problem as an abstract and discrete decision-making problem involving multiple actions, multiple actors with preconceived gains and losses with respect to the comprising actions, and decisions as combinations of actions. Using fictitious and yet realistic scenarios and stakeholders as simulation, the results evidence how different levels of democratic participation and different modes of moderation can affect reaching a consensus and present in a mathematical characterisation of a consensus as a state of equilibrium. The small set of actions and actors enabled a chance to compute a theoretically optimal state of consensus, where the efficiency and the effectiveness of different modes of moderation and participatory rights could be observed and analysed.
keywords	Serious Game; Consensus Building; Democratization; Game Theory; Social Decision
series	eCAADe
email
last changed	2022/06/07 07:54

_id	837c
authors	Ball, L.J., Lambell, N.J., Ormerod, Th.C., Slavin, S. and Mariani, John A.
year	2001
title	Representing design rationale to support innovative design reuse: a minimalist approach
source	Automation in Construction 10 (6) (2001) pp. 663-674
summary	The reuse of previous design knowledge is a potentially important way to improve design efficiency. In practice, however, design reuse is plagued with difficulties, including those associated with the indexing, retrieval, understanding and modification of prior design knowledge. We propose that such difficulties can be ameliorated by employing insights deriving from design-rationale research concerning how best to represent and retrieve design information. We illustrate these insights by describing the development of a design-reuse system that maximizes the benefits of rationale capture and information retrieval whilst minimising the costs to the designer that might arise from disruption to natural design work.
series	journal paper
more	http://www.elsevier.com/locate/autcon
last changed	2003/05/15 21:22

_id	sigradi2023_508
id	sigradi2023_508
authors	Barber, Gabriela and Lafluf, Marcos
year	2023
title	Videomapping laboratory. Systematization of experiences 2016-2022
source	García Amen, F, Goni Fitipaldo, A L and Armagno Gentile, Á (eds.), Accelerated Landscapes - Proceedings of the XXVII International Conference of the Ibero-American Society of Digital Graphics (SIGraDi 2023), Punta del Este, Maldonado, Uruguay, 29 November - 1 December 2023, pp. 843–854
summary	This article synthesizes the result of a systematization and analysis of videomapping carried out in “Laboratorio de Visualización Digital Avanzada” in the period 2014-2022, taking as a source the information collected in the investigation "(Lafluf, 2020), it is updated by integrating new experiences and new interpretations. Likewise, the article aims to provide a structured way to describe and analyze videomapping projects, keeping in mind three axes: context project, mapping project, and mapping event. These categories refer to a strategy developed within the methodological framework of the master's thesis "Videomapping en los proyectos del Laboratorio de Visualización Digital Avanzada de la Facultad de Arquitectura Diseno y Urbanismo (Udelar). Caso de estudio: Videomapping Patrimonio Anglo" (Lafluf, 2020) as well as in other investigations to describe the videomapping. Once this set of videomapping projects has been presented, general considerations are made to analyze the surveyed cases.
keywords	New Media Art, video mapping, New Media, Architecture, Projection Mapping
series	SIGraDi
email
last changed	2024/03/08 14:07

_id	cf2017_337
id	cf2017_337
authors	Barber, Gabriela; Lafluf, Marcos; Amen, Fernando Garcia; Accuosto, Pablo
year	2017
title	Interactive Projection Mapping in Heritage: The Anglo Case
source	Gülen Çagdas, Mine Özkar, Leman F. Gül and Ethem Gürer (Eds.) Future Trajectories of Computation in Design [17th International Conference, CAAD Futures 2017, Proceedings / ISBN 978-975-561-482-3] Istanbul, Turkey, July 12-14, 2017, pp. 337-348.
summary	This work is the outcome of a multidisciplinary collaboration in the context of the VidiaLab (Laboratorio de Visualización Digital Avanzada). It proposes an application of interactive video mapping techniques as a form of experiencing the Fray Bentos industrial landscape, declared as a World Heritage Site by UNESCO in 2015. An immersive environment was created by enriching a physical scale model of the site with projected digital images and information, providing new and attractive ways of interaction with the cultural heritage. Proposals for future work and educational applications of the developed tools are also discussed.
keywords	Video Mapping, New Media Art, Heritage, Museum, Human-Computer Interaction
series	CAAD Futures
email
last changed	2017/12/01 14:38

_id	c0ee
authors	Bentley, Jon L. and Ottmann, Thomas
year	1981
title	The Complexity of Manipulating Hierarchically Defined Sets of Rectangles
source	40 p. : ill. Pittsburgh, PA: Department of Computer Science, CMU., April, 1981. CMU-CS-81-109. includes bibliography
summary	Algorithms that manipulate sets of rectangles are of great practical importance in VLSI design systems and other applications. Although much theoretical work has appeared recently on the complexity of rectangle problems, it has assumed that the inputs are given as a list of rectangles. In this paper the authors study the complexity of rectangle problems when the inputs are given in a hierarchical language that allows the designer to build large designs by replicating small designs. They show that while most of the problems are NP-hard in the general case, there are O(N log N) algorithms that process inputs obeying certain restrictions
keywords	rectangles, algorithms, computational geometry, data structures
series	CADline
last changed	2003/06/02 10:24

_id	e671
authors	Bentley, Jon L., Haken, Dorothea and Saxe, James B.
year	1978
title	A General Method for Solving Divide-and-Conquer Recurrences
source	10 p Carnegie Mellon University: December, 1978. includes bibliography.
summary	The complexity of divide-and-conquer algorithms is often described by recurrence relations of the form T(n) = kT(n/c) + f(n). The only method currently available for solving such recurrences consists of solution tables for fixed functions f and varying k and c. In this note the authors describe a unifying method for solving these recurrences that is both general in applicability and easy to apply without the use of large tables
keywords	recursion, algorithms, divide-and-conquer
series	CADline
last changed	2003/06/02 13:58

_id	ca8e
authors	Bentley, Jon L.
year	1975
title	Multidimensional Binary Search Trees Used for Associative Searching
source	communications of the ACM September, 1975. vol. 18: pp. 509-517 : ill. includes bibliography.
summary	This paper develops the multidimensional binary search tree (or k-d tree, where k is the dimensionality of the search space) as a data structure for storage of information to be retrieved by associative searches. The k-d tree is defined and examples are given. It is shown to be quite efficient in its storage requirements. A significant advantage of this structure is that a single data structure can handle many types of queries very efficiently. Various utility algorithms are developed; their proven average running times in an n record file are: insertion, O(log(n)); deletion of the root, O(n(k-1)/k); deletion of a random node, O(n); and optimization (guarantees logarithmic performance of searches), O(n(log(n))). Search algorithms are given for partial match queries with t keys specified [proven maximum running time of O(n(k-t)/k)] and for nearest neighbor queries [empirically observed average running time of O(log n).] These performances far surpass the best currently known algorithms for these tasks. An algorithm is presented to handle any general intersection query. The main focus of this paper is theoretical. It is felt, however, that k-d trees could be quite useful in many applications, and examples of potential uses are given
keywords	search, attributes, information, systems, queries, database, intersection, algorithms
series	CADline
last changed	2003/06/02 13:58

For more results click below: