Descripteur
Termes IGN > mathématiques > analyse mathématique > topologie > théorie des graphes > graphe > arbre (mathématique)
arbre (mathématique) |
Documents disponibles dans cette catégorie (138)
Ajouter le résultat dans votre panier
Visionner les documents numériques
Affiner la recherche Interroger des sources externes
Etendre la recherche sur niveau(x) vers le bas
Spatial databases : with applications to GIS / Philippe Rigaux (2001)
Titre : Spatial databases : with applications to GIS Type de document : Guide/Manuel Auteurs : Philippe Rigaux, Auteur Editeur : San Francisco : Morgan Kaufmann Publishers Année de publication : 2001 Importance : 408 p. Format : 19 x 24 cm ISBN/ISSN/EAN : 978-1-55860-588-6 Note générale : Bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Bases de données localisées
[Termes IGN] arbre quadratique
[Termes IGN] arbre-B
[Termes IGN] arbre-R
[Termes IGN] ArcInfo
[Termes IGN] ArcView
[Termes IGN] base de données localisées
[Termes IGN] données localisées
[Termes IGN] modèle orienté objet
[Termes IGN] Oracle spatial
[Termes IGN] PostgreSQL
[Termes IGN] représentation spatiale
[Termes IGN] requête spatiale
[Termes IGN] Smallworld
[Termes IGN] système d'information géographiqueRésumé : (Editeur) This book covers all of the major themes of the field-representation, query languages, computational geometry, spatial indexing-using geographic information systems as the principal application domain and motivation. It is an excellent introduction for computer science professionals interested in exploring GIS, and an excellent resource for GIS professionals interested in learning more about the computer science foundations of the field.
This book is a well-written, comprehensive treatment of a multidisciplinary field, spanning computational geometry, database modeling, object-orientation, and query processing. The book presents both advanced research and commercial systems in a clear and accessible manner. It is the first unified, in-depth treatment of special techniques for dealing with spatial data, particularly in the field of geographic information systems (GIS). This book surveys various techniques, such as spatial data models, algorithms, and indexing methods, developed to address specific features of spatial data that are not adequately handled by mainstream DBMS technology.
The book also reviews commercial solutions to geographic data handling: Arcinfo, ArcView, and Srnallworld GISs; and two extensions to the relational model, PostgreSQL and Oracle Spatial. The authors examine these underlying GIS technologies, assess their strengths and weaknesses, and consider specific uses for which pach product is best suited.
It examines the strengths of various query languages and approaches to query processing. It explains the use of computational geometry in spatial databases GISs, providing necessary background and an indepth look at key algorithms. It covers spatial access methods, including the R-tree and several space-driven structures, and is filled with dozens of helpful illustrations.Note de contenu : 1 - AN INTRODUCTION TO SPATIAL DATABASES
Database Management Systems (DBMSs)
Basic Description and Main Features
Modeling Applications
Physical Data Management
Vocabulary in Geospatial Database Applications
Theme
Geographic Objects
Geospatial Data Manipulation
Simple Operations on Themes
Further Theme Operations
Other Typical GIS Operations
DBMS Support for Geospatial Data
Use of a Relational DBMS
Loosely Coupled Approach
Integrated Approach Based on DBMS Extensibility
Requirements for a Spatial DBMS
Bibliographic Notes
2 - REPRESENTATION OF SPATIAL OBJECTS
Geographic Space Modeling
EntityBased Models
FieldBased Models
Representation Modes
Tessellation
Vector Mode
HalfPlane Representation
Representing the Geometry of a Collection of Objects
Spaghetti Model
Network Model
Topological Model
Spatial Data Formats and Exchange Standards
Overview of Current Spatial Data Formats
The TIGER/Line Data Format
Recent Standardization Initiatives
Bibliographic Notes
3 - LOGICAL MODELS AND QUERY LANGUAGES
Reference Schemas
Administrative Units (Schema 1)
Highway Network Among Cities (Schema 2)
Land Use (Schema 3)
Reference Queries Spatial Abstract Data Types
Extending Data Models with Spatial ADTs
Designing Spatial ADTs
Exploring Relationships Between Spatial Objects: Topological Predicates
Relational Models Extended with ADT
Representation of the Reference Schemas
Reference Queries
ObjectOriented Models
A Brief Overview of ObjectOriented DBMS
Representation of Reference Schemas
Spatial Classes
Reference Queries
Bibliographic Notes
4 - THE CONSTRAINT DATA MODEL
Spatial Data Modeling with Constraints
Point Sets as Infinite Relations
Finitely Representing Infinite Relations
Evaluating Queries on Infinite Instances
Summary of the Constraint Data Model
The Linear Constraint Data Model
Data Representation
Query Languages: First-Order Queries
Query Languages: Algebraic Queries
Modeling EntityBased Data
Nested Relations
Queries
Modeling FieldBased Data and Moving Objects
Elevation Data
Moving Objects
Queries on FieldBased Data and Moving Points
Bibliographic Notes
5 - COMPUTATIONAL GEOMETRY
An Introduction to Computational Geometry
Background
Basic Concepts of Algorithms
Algorithm Analysis
Optimality
Data Structures
Useful Algorithmic Strategies
Incremental Algorithms: The Convex-Hull Example
DivideandConquer Strategy: The HalfPlane Intersection Example
SweepLine Method: The Rectangle Intersection Example
Polygon Partitioning
Trapezoidalization of a Simple Polygon
Triangulation of Simple Polygons
Convex Partitioning
Algorithms for Spatial Databases
Area Size of a Polygon and Related Operations
Point in Polygon
Polyline Intersections
Polygon Intersections
Windowing and Clipping
Bibliographic Notes
General Sources
Sources on Algorithms
6 - SPATIAL ACCESS METHODS
Issues in SAM Design
What Is Expected of a SAM ?
Illustration with a B-Tree
SpaceDriven Versus DataDriven SAMs
SpaceDriven Structures
The Grid File
The Linear Quadtree
The zOrdering Tree
Remarks on Linear SAM
DataDriven Structures: The RTree
The Original RTree
The R*Tree
R-Tree Packing
The R+Tree
Cost Models
Bibliographic Notes
7 - QUERY PROCESSING
An Introduction to Query Processing
Two Optimal I/O Algorithms
External Sort/Merge
Distribution Sweeping (Rectangle Intersection)
Spatial Join
zOrdering Spatial Join
Joining Two RTrees
Spatial Hash Join
Complex Queries
Query Execution Plans
Spatial Joins with Refinement Step
Multiway Joins
Bibliographic Notes
8 - COMMERCIAL SYSTEMS
An Introduction to Commercial Systems
How to Read This Chapter
Interacting with a GIS or with a Spatial DBMS
Arclnfo
Functionalities of Arclnfo
Spatial and Topological Information in Arclnfo
Representation of Sample Schemas
Querying with Arclnfo
ArcView GIS
ArcView Spatial Model
Querying with ArcView
Smallworld
Smallworld Spatial Data Model
Querying with Smallworld Object Browser
Discussion
Oracle Extension for Handling Spatial Data
Introduction to Oracle Spatial
Spatial Data Model
Spatial Operations
Spatial Indexing and Query Processing
PostgreSQL,
Geometric Types and Operators
Creating the Database
Expressing Queries
Bibliographic NotesNuméro de notice : 69415 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE/INFORMATIQUE Nature : Manuel de cours Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=62189 Réservation
Réserver ce documentExemplaires(3)
Code-barres Cote Support Localisation Section Disponibilité 69415-02 37.10 Livre Centre de documentation Géomatique Disponible 69415-03 37.10 Livre Centre de documentation Géomatique Disponible 69415-01 DEP-ELD Livre Marne-la-Vallée Dépôt en unité Exclu du prêt
contenu dans Advances in spatial data bases, SSD '99, 6th International Symposium, Hong Kong, China, July 20-23, 1999 / Ralf Hartmut Güting (1999)
Titre : Algorithms for joining R-trees and linear region quadtrees Type de document : Article/Communication Auteurs : A. Corral, Auteur ; M. Vassilakopoulos, Auteur ; Y. Manolopoulos, Auteur Editeur : Berlin, Heidelberg, Vienne, New York, ... : Springer Année de publication : 20/07/1999 Conférence : SSD 1999, 6th International Symposium Advances in spatial data bases 20/07/1999 23/07/1999 Hong Kong Chine Proceedings Springer Importance : pp 251 - 269 Note générale : Bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Bases de données localisées
[Termes IGN] accès aux données localisées
[Termes IGN] arbre quadratique
[Termes IGN] arbre-R
[Termes IGN] base de données localisées
[Termes IGN] jointure spatiale
[Termes IGN] requête spatialeRésumé : (Auteur) The family of R-trees is suitable for storing various kinds of multidimensional objects and is considered an excellent choice for indexing a spatial database. Region Quadtrees are suitable for storing 2-dimensional regional data and their linear variant is used in many Geographical Information Systems for this purpose. In this report, we present five algorithms suitable for processing join queries between these two successful, although very different, access methods. Two of the algorithms axe based on heuristics that aim at minimizing I/O cost with a limited amount of main memory. We also present the results of experiments performed with real data that compare the I/O performance of these algorithms. Numéro de notice : C1999-060 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE/INFORMATIQUE Nature : Communication DOI : 10.1007/3-540-48482-5_16 En ligne : https://doi.org/10.1007/3-540-48482-5_16 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=65826
contenu dans Advances in spatial data bases, SSD '99, 6th International Symposium, Hong Kong, China, July 20-23, 1999 / Ralf Hartmut Güting (1999)
Titre : GBI : a generalized R-tree bulk-insertion strategy Type de document : Article/Communication Auteurs : R. Choubey, Auteur ; L. Chen, Auteur ; E.A. Rundensteiner, Auteur Editeur : Berlin, Heidelberg, Vienne, New York, ... : Springer Année de publication : 20/07/1999 Collection : Lecture notes in Computer Science, ISSN 0302-9743 num. 1651 Conférence : SSD 1999, 6th International Symposium Advances in spatial data bases 20/07/1999 23/07/1999 Hong Kong Chine Proceedings Springer Importance : pp 91 - 108 Note générale : Bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Bases de données localisées
[Termes IGN] arbre-R
[Termes IGN] groupe
[Termes IGN] index spatial
[Termes IGN] indexation spatiale
[Termes IGN] requête spatialeRésumé : (Auteur) A lot of recent work has studied strategies related to bulk loading of large data sets into multidimensional index structures. In this paper, we address the problem of bulk insertions into existing index structures with particular focus on R-trees - which are an important class of index structures used widely in commercial database systems. We propose a new technique, which as opposed to the current technique of inserting data one by one, bulk inserts entire new incoming datasets into an active R-tree. This technique, called GBI (for Generalized Bulk Insertion), partitions the new datasets into sets of clusters and outliers, constructs an R-tree (small tree) from each cluster, identifies and prepares suitable locations in the original R.-tree (large tree) for insertion, and lastly performs the insertions of the small trees and the outliers into the large tree in bulk. Our experimental studies demonstrate that GBI does especially well (over 200% better than the existing technique) for randomly located data as well as for real datasets that contain few natural clusters, while also consistently outperforming the alternate technique in all other circumstances. Numéro de notice : C1999-057 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE/INFORMATIQUE Nature : Communication DOI : 10.1007/3-540-48482-5_8 En ligne : https://doi.org/10.1007/3-540-48482-5_8 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=65823
Titre : Généralisation du bâti : structure spatiale de type graphe et représentation cartographique Type de document : Thèse/HDR Auteurs : Nicolas Regnauld , Auteur ; Robert Jeansoulin, Directeur de thèse Editeur : Marseille : Université de Provence Aix-Marseille 1 Année de publication : 1998 Importance : 188 p. Format : 21 x 30 cm Note générale : Bibliographie
Thèse pour obtenir le grade de docteur de l'université de Provence, discipline informatiqueLangues : Français (fre) Descripteur : [Termes IGN] analyse spatiale
[Termes IGN] arbre (mathématique)
[Termes IGN] bati
[Termes IGN] généralisation cartographique automatisée
[Termes IGN] graphe
[Termes IGN] index spatial
[Termes IGN] représentation cartographique
[Vedettes matières IGN] GénéralisationIndex. décimale : THESE Thèses et HDR Résumé : (Auteur) La base de données topographique de l'Institut Géographique National (BDTOPO) est actuellement utilisée à diverses fins dont la production des cartes au 1 : 25 000. Une extension possible serait de dériver aussi des cartes à de plus petites échelles (notamment au 1 : 50 000) et ce, de manière automatique. Le principal obstacle à cette automatisation est la phase de généralisation cartographique, qui doit extraire de la base, l'information pertinente pour la nouvelle échelle. D'une manière plus générale, cette fonctionnalité importante des Systèmes d'Information Géographique, n'est présente à l'heure actuelle que sous la forme d'outils spécifiques proposés à l'utilisateur du système pour traiter des cas précis.
On peut faire l'analogie par exemple avec la génération automatique de résumé de texte : la généralisation est à la carte ce que le résumé de texte est au texte, il ne s'agit pas de jouer sur la taille des caractères, mais de supprimer ce qui n'est pas essentiel, de regrouper et réduire les développements tout en conservant leur sens, parfois de conserver ce qui est exceptionnel.
Nous avons limité le contexte de nos recherches au cas du bâti, avec pour objectif d'identifier les liens qui existent entre les données initiales et leurs représentations graphiques à une échelle plus petite. Le but est ensuite de définir un outil automatique pour associer, à un lot de données représentant une zone de bâti dense, une représentation graphique adaptée à une échelle donnée.
La première partie est consacrée à la modélisation de la perception visuelle des groupements de bâtiments sur une carte. Le but est d'extraire les structures qui sont visuellement repérables. On utilise pour cela un graphe de plus proche voisinage sur les bâtiments, sur lequel on fait des mesures selon des critères issus de la théorie de "Gestalt " (perception de groupes). Le résultat de cette analyse fournit l'information géographique associée à chacune des structures, c'est à dire leur caractère : taille moyenne des bâtiments, forme du groupe, densité ... Ces informations sont indépendantes de l'échelle. A partir de ces structures, nous définissons une méthode permettant de leur associer d'autres représentations à différentes échelles.
Nous avons enfin défini des méthodes d'évaluation du résultat permettant d'assurer la bonne intégration du processus dans un système de généralisation automatique. Les éventuelles dégradations constatées sont évaluées et stockées au niveau des objets de la classe structure.
La modélisation des structures et leur stockage permettent au processus global lorsqu'il effectue des modifications individuelles sur un bâtiment (déplacement), de déterminer à quelle structure il appartient et de vérifier que les modifications n'ont pas dégradé la perceptibilité de la structure. Si une dégradation est survenue, alors un traitement local au groupe peut être entrepris. La structure peut donc servir d'index spatial "intelligent" pour accéder aux bâtiments.Numéro de notice : 11623 Affiliation des auteurs : COGIT (1988-2011) Thématique : GEOMATIQUE Nature : Thèse française Note de thèse : Thèse de doctorat : informatique : Provence Aix-Marseille 1 : 1998 Organisme de stage : COGIT (IGN) nature-HAL : Thèse DOI : sans Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=45163 Réservation
Réserver ce documentExemplaires(6)
Code-barres Cote Support Localisation Section Disponibilité 11623-03 THESE Livre Centre de documentation Thèses Disponible 11623-02 THESE Livre Centre de documentation Thèses Disponible 11623-01 THESE Livre Centre de documentation Thèses Disponible 11623-04 THESE Livre Centre de documentation Thèses Disponible 11623-06 K325 Livre LASTIG Dépôt en unité Exclu du prêt 11623-05 K325 Livre LASTIG Dépôt en unité Exclu du prêt Documents numériques
peut être téléchargé
Généralisation du bâti... - pdf auteur-Adobe Acrobat PDF Triangulation de Delaunay et arbres multidimensionnels / Christophe Lemaire (1997)
Titre : Triangulation de Delaunay et arbres multidimensionnels Type de document : Thèse/HDR Auteurs : Christophe Lemaire, Auteur Editeur : Saint-Etienne : Université Jean-Monnet-Saint-Etienne Année de publication : 1997 Importance : 208 p. Format : 21 x 30 cm Note générale : bibliographie Langues : Français (fre) Descripteur : [Vedettes matières IGN] Algorithmique
[Termes IGN] arbre (mathématique)
[Termes IGN] arbre k-d
[Termes IGN] arbre quadratique
[Termes IGN] complexité
[Termes IGN] diagramme de Voronoï
[Termes IGN] géomètrie algorithmique
[Termes IGN] triangulation de DelaunayIndex. décimale : THESE Thèses et HDR Résumé : (auteur) Les travaux effectués lors de cette thèse concernent principalement la triangulation de Delaunay. On montre que la complexité en moyenne - en termes de sites inachevés - du processus de fusion multidimensionnelle dans l'hypothèse de distribution quasi-uniforme dans un hypercube est linéaire en moyenne. Ce résultat général est appliqué au cas du plan et permet d'analyser de nouveaux algorithmes de triangulation de Delaunay plus performants que ceux connus à ce jour. Le principe sous-jacent est de diviser le domaine selon des arbres bidimensionnels (quadtree, 2d-tree, bucket-tree …), puis de fusionner les cellules obtenues selon deux directions. On étudie actuellement la prise en compte de contraintes directement pendant la phase de triangulation avec des algorithmes de ce type. De nouveaux algorithmes pratiques de localisation dans une triangulation sont proposés, basés sur la randomisation à partir d'un arbre binaire de recherche dynamique de type AVL, dont l'un est plus rapide que l'algorithme optimal de. Kirkpatrick, au moins jusqu'à 12 millions de sites ! Nous travaillons actuellement sur l'analyse rigoureuse de leur complexité en moyenne. Ce nouvel algorithme est utilisé pour construire "en-ligne" une triangulation de Delaunay qui est parmi les plus performantes des méthodes "en-ligne" connues à ce jour. Numéro de notice : 17244 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE/INFORMATIQUE/MATHEMATIQUE Nature : Thèse française Note de thèse : thèse de doctorat : Informatique : Saint-Etienne : 1997 Organisme de stage : SETRA nature-HAL : Thèse DOI : sans Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=81629 Réservation
Réserver ce documentExemplaires(1)
Code-barres Cote Support Localisation Section Disponibilité 17244-01 THESE Livre Centre de documentation Thèses Disponible Conception et réalisation d'un SGBD géographique orienté-objet et étude des problèmes spécifiques à l'indexation spatiale / J.P. Peloux (1996)PermalinkEnrichissement des bases de données géographiques / Corinne Plazanet (1996)PermalinkLes bases de données relationnelles / Imad Saleh (1994)PermalinkSDH 94, Sixth international symposium on Spatial Data Handling, 5th - 9th September 1994, Edinburgh, Scotland, UK: Advances in GIS research, Vol 2. Proceedings / Thomas C. Waugh (1994)PermalinkSPATIO2 : un modèle orienté objet généralisé pour les systèmes d'informations spatiales / Mohamed El Adnani (1994)PermalinkTest d'implémentations de l'opérateur d'agrégation sur le SIG Smallworld pour un modèle hiérarchique de données traitant de zones végétales des Hautes-Alpes / Claudine Derrac (1994)PermalinkSpace at the Service of our environment: Proceedings of the First ERS-1 Symposium, 4-6 November 1992, Cannes, France, 2. Volume 2 / B. Kaldeich (1993)PermalinkModellierung geometrisch-topologischer Daten zur Beschreibung und Berechnung netzartiger und flächenhafter Strukturen / M. Neureither (1992)PermalinkTime in Geographic Information Systems / G. Langran (1992)PermalinkThe hB-tree: a multiattribute indexing method with good guaranteed performance / David Bruce Lomet in ACM Transactions on database systems, TODS, vol 15 n° 4 (December 1990)Permalink