To see the other types of publications on this topic, follow the link: Search in graphs AND.
Dissertations / Theses on the topic 'Search in graphs AND'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Search in graphs AND.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Habi, Abdelmalek. "Search and Aggregation in Big Graphs." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSE1259/document.
Full textAbstract:
Ces dernières années ont connu un regain d'intérêt pour l'utilisation des graphes comme moyen fiable de représentation et de modélisation des données, et ce, dans divers domaines de l'informatique. En particulier, pour les grandes masses de données, les graphes apparaissent comme une alternative prometteuse aux bases de données relationnelles. Plus particulièrement, le recherche de sous-graphes s'avère être une tâche cruciale pour explorer ces grands jeux de données. Dans cette thèse, nous étudions deux problématiques principales. Dans un premier temps, nous abordons le problème de la détection de motifs dans les grands graphes. Ce problème vise à rechercher les k-meilleures correspondances (top-k) d'un graphe motif dans un graphe de données. Pour cette problématique, nous introduisons un nouveau modèle de détection de motifs de graphe nommé la Simulation Relaxée de Graphe (RGS), qui permet d’identifier des correspondances de graphes avec un certain écart (structurel) et ainsi éviter le problème de réponse vide. Ensuite, nous formalisons et étudions le problème de la recherche des k-meilleures réponses suivant deux critères, la pertinence (la meilleure similarité entre le motif et les réponses) et la diversité (la dissimilarité entre les réponses). Nous considérons également le problème des k-meilleures correspondances diversifiées et nous proposons une fonction de diversification pour équilibrer la pertinence et la diversité. En outre, nous développons des algorithmes efficaces basés sur des stratégies d’optimisation en respectant le modèle proposé. Notre approche est efficiente en terme de temps d’exécution et flexible en terme d'applicabilité. L’analyse de la complexité des algorithmes et les expérimentations menées sur des jeux de données réelles montrent l’efficacité des approches proposées. Dans un second temps, nous abordons le problème de recherche agrégative dans des documents XML. Pour un arbre requête, l'objectif est de trouver des motifs correspondants dans un ou plusieurs documents XML et de les agréger dans un seul agrégat. Dans un premier temps nous présentons la motivation derrière ce paradigme de recherche agrégative et nous expliquons les gains potentiels par rapport aux méthodes classiques de requêtage. Ensuite nous proposons une nouvelle approche qui a pour but de construire, dans la mesure du possible, une réponse cohérente et plus complète en agrégeant plusieurs résultats provenant de plusieurs sources de données. Les expérimentations réalisées sur plusieurs ensembles de données réelles montrent l’efficacité de cette approche en termes de pertinence et de qualité de résultat<br>Recent years have witnessed a growing renewed interest in the use of graphs as a reliable means for representing and modeling data. Thereby, graphs enable to ensure efficiency in various fields of computer science, especially for massive data where graphs arise as a promising alternative to relational databases for big data modeling. In this regard, querying data graph proves to be a crucial task to explore the knowledge in these datasets. In this dissertation, we investigate two main problems. In the first part we address the problem of detecting patterns in larger graphs, called the top-k graph pattern matching problem. We introduce a new graph pattern matching model named Relaxed Graph Simulation (RGS), to identify significant matches and to avoid the empty-set answer problem. We formalize and study the top-k matching problem based on two classes of functions, relevance and diversity, for ranking the matches according to the RGS model. We also consider the diversified top-k matching problem, and we propose a diversification function to balance relevance and diversity. Moreover, we provide efficient algorithms based on optimization strategies to compute the top-k and the diversified top-k matches according to the proposed model. The proposed approach is optimal in terms of search time and flexible in terms of applicability. The analyze of the time complexity of the proposed algorithms and the extensive experiments on real-life datasets demonstrate both the effectiveness and the efficiency of these approaches. In the second part, we tackle the problem of graph querying using aggregated search paradigm. We consider this problem for particular types of graphs that are trees, and we deal with the query processing in XML documents. Firstly, we give the motivation behind the use of such a paradigm, and we explain the potential benefits compared to traditional querying approaches. Furthermore, we propose a new method for aggregated tree search, based on approximate tree matching algorithm on several tree fragments, that aims to build, the extent possible, a coherent and complete answer by combining several results. The proposed solutions are shown to be efficient in terms of relevance and quality on different real-life datasets
2
Varadarajan, Ramakrishna R. "Ranked Search on Data Graphs." FIU Digital Commons, 2009. http://digitalcommons.fiu.edu/etd/220.
Full textAbstract:
Graph-structured databases are widely prevalent, and the problem of effective search and retrieval from such graphs has been receiving much attention recently. For example, the Web can be naturally viewed as a graph. Likewise, a relational database can be viewed as a graph where tuples are modeled as vertices connected via foreign-key relationships. Keyword search querying has emerged as one of the most effective paradigms for information discovery, especially over HTML documents in the World Wide Web. One of the key advantages of keyword search querying is its simplicity – users do not have to learn a complex query language, and can issue queries without any prior knowledge about the structure of the underlying data. The purpose of this dissertation was to develop techniques for user-friendly, high quality and efficient searching of graph structured databases. Several ranked search methods on data graphs have been studied in the recent years. Given a top-k keyword search query on a graph and some ranking criteria, a keyword proximity search finds the top-k answers where each answer is a substructure of the graph containing all query keywords, which illustrates the relationship between the keyword present in the graph. We applied keyword proximity search on the web and the page graph of web documents to find top-k answers that satisfy user’s information need and increase user satisfaction. Another effective ranking mechanism applied on data graphs is the authority flow based ranking mechanism. Given a top-k keyword search query on a graph, an authority-flow based search finds the top-k answers where each answer is a node in the graph ranked according to its relevance and importance to the query. We developed techniques that improved the authority flow based search on data graphs by creating a framework to explain and reformulate them taking in to consideration user preferences and feedback. We also applied the proposed graph search techniques for Information Discovery over biological databases. Our algorithms were experimentally evaluated for performance and quality. The quality of our method was compared to current approaches by using user surveys.
3
Janmark, Jonatan. "Quantum Search on Strongly Regular Graphs." Thesis, KTH, Teoretisk fysik, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-126266.
Full text
4
Trippen, Gerhard Wolfgang. "Online exploration and search in graphs /." View abstract or full-text, 2006. http://library.ust.hk/cgi/db/thesis.pl?COMP%202006%20TRIPPE.
Full text
5
Korneffel, Torsten. "On combinatorial search problems which involve graphs." [S.l.] : [s.n.], 2007. http://deposit.ddb.de/cgi-bin/dokserv?idn=984062386.
Full text
6
Yuan, Wenjun, and 袁文俊. "Flexgraph: flexible subgraph search in large graphs." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2010. http://hub.hku.hk/bib/B46087539.
Full text
7
Jiang, Jiaxin. "Efficient frameworks for keyword search on massive graphs." HKBU Institutional Repository, 2020. https://repository.hkbu.edu.hk/etd_oa/806.
Full textAbstract:
Due to the unstructuredness and the lack of schema information of knowledge graphs, social networks and RDF graphs, keyword search has been proposed for querying such graphs/networks. Recently, various keyword search semantics have been designed. However, these keyword search semantics and algorithms encounter efficiency or scalability issues. In this thesis, we propose new three generic frameworks or index techniques to address these issues. The thesis results show that the keyword search on massive graphs under different scenarios can be effective and efficient, which would facilitate keyword search services on graphs in the real world. First, we study the keyword search on massive knowledge graphs. In particular, we propose a generic ontology- based indexing framework for keyword search, called Bisimulation of Generalized Graph Index (BiG-index), to enhance the search performance. The novelties of BiG-index reside in using an ontology graph GOnt to summarize and index a data graph G iteratively, to form a hierarchical index structure G. Regarding query evaluation, we transform a keyword search q into Q according to GOnt in runtime. The transformed query is searched on the summary graphs in G. The efficiency is due to the small sizes of the summary graphs and the early pruning of semantically irrelevant subgraphs. To illustrate BiG-index's applicability, we show popular indexing techniques for keyword search can be easily implemented on top of BiG-index. Our extensive experiments show that BiG-index clearly reduced the runtimes of popular keyword search algorithms. Second, we study the problem of keyword search on public-private graph. In many applications (e.g., social networks), users may prefer to hide parts or all of her/his data graphs (e.g., private friendships) from the public. This leads to a recent graph model, namely the public-private network model, in which each user has his/her own network. While there have been studies on public-private network analysis, keyword search on public-private networks has not yet been studied. Hence, we propose a new keyword search framework, called public-private keyword search (PPKWS). PPKWS consists of three major steps: partial evaluation, answer refinement, and answer completion. We select three representative ones and show that they can be implemented on the model with minor modifications. We propose indexes and optimizations for PPKWS. We have verified through experiments that, on average, the algorithms implemented on top of PPKWS run 113 times faster than the original algorithms directly running on the public network attached to the private network for retrieving answers that span through them. Third, we study the keyword search in distributed graph evaluation systems. In the recent research on query evaluation, parallel evaluation has attracted much interest. However, the study on keyword search on distributed graphs has still been limited. We propose a novel distributed keyword search framework called DKWS. We propose a notify-push paradigm which can exchange the upper bounds of answers across all the workers asynchronously. In particular, the workers notify the coordinator when the local upper bound is refined. The coordinator pushes the refined global upper bound to all the workers. Moreover, we propose an efficient and generic keyword search algorithm for the workers. We have implemented DKWS on top of GRAPE, a distributed graph process system from our previous research collaboration. Extensive experimental results show that DKWS outperforms current-state-of-art techniques
8
Hunter, Andrew. "Locality and Complexity in Path Search." Scholarship @ Claremont, 2009. https://scholarship.claremont.edu/hmc_theses/220.
Full textAbstract:
The path search problem considers a simple model of communication networks as channel graphs: directed acyclic graphs with a single source and sink. We consider each vertex to represent a switching point, and each edge a single communication line. Under a probabilistic model where each edge may independently be free (available for use) or blocked (already in use) with some constant probability, we seek to efficiently search the graph: examine (on average) as few edges as possible before determining if a path of free edges exists from source to sink. We consider the difficulty of searching various graphs under different search models, and examine the computational complexity of calculating the search cost of arbitrary graphs.
9
Marshall, Oliver. "Search Engine Optimization and the connection with Knowledge Graphs." Thesis, Högskolan i Gävle, Företagsekonomi, 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:hig:diva-35165.
Full textAbstract:
Aim: The aim of this study is to analyze the usage of Search Engine Optimization and Knowledge Graphs and the connection between them to achieve profitable business visibility and reach. Methods: Following a qualitative method together with an inductive approach, ten marketing professionals were interviewed via an online questionnaire. To conduct this study both primary and secondary data was utilized. Scientific theory together with empirical findings were linked and discussed in the analysis chapter. Findings: This study establishes current Search Engine Optimization utilization by businesses regarding common techniques and methods. We demonstrate their effectiveness on the Google Knowledge Graph, Google My Business and resulting positive business impact for increased visibility and reach. Difficulties remain in accurate tracking procedures to analyze quantifiable results. Contribution of the thesis: This study contributes to the literature of both Search Engine Optimization and Knowledge Graphs by providing a new perspective on how these subjects have been utilized in modern marketing. In addition, this study provides an understanding of the benefits of SEO utilization on Knowledge Graphs. Suggestions for further research: We suggest more extensive investigation on the elements and utilization of Knowledge Graphs; how the structure can be affected; which techniques are most effective on a bigger scale and how effectively the benefits can be measured. Key Words: Search Engine, Search Engine Optimization, SEO, Knowledge Graphs, Google My Business, Google Search Engine, Online Marketing.
10
Chen, Yan. "Enhanced Web Search Engines with Query-Concept Bipartite Graphs." Digital Archive @ GSU, 2010. http://digitalarchive.gsu.edu/cs_diss/54.
Full textAbstract:
With rapid growth of information on the Web, Web search engines have gained great momentum for exploiting valuable Web resources. Although keywords-based Web search engines provide relevant search results in response to users’ queries, future enhancement is still needed. Three important issues include (1) search results can be diverse because ambiguous keywords in queries can be interpreted to different meanings; (2) indentifying keywords in long queries is difficult for search engines; and (3) generating query-specific Web page summaries is desirable for Web search results’ previews. Based on clickthrough data, this thesis proposes a query-concept bipartite graph for representing queries’ relations, and applies the queries’ relations to applications such as (1) personalized query suggestions, (2) long queries Web searches and (3) query-specific Web page summarization. Experimental results show that query-concept bipartite graphs are useful for performance improvement for the three applications.
11
Dawson, Jessica Quinn. "A search set model of path tracing in graphs." Thesis, University of British Columbia, 2013. http://hdl.handle.net/2429/45404.
Full textAbstract:
Path tracing is a common task in many real world uses of graphs that display networks of relationships. Despite previous work in the evaluation of how factors, such as edge-edge crossings, impact the readability of graph layouts, what makes one path-tracing task more difficult than another is not well understood.
To address this question we conducted an observational user study with 12 participants completing a path-tracing task. Our extensive qualitative analysis of the study data led to a detailed characterization of common path-tracing behaviours. We then created a predictive model of the paths that users are most likely to search, which we name the search set, based on the behaviours we observed. To validate our predictive behavioural model, and to demonstrate how the search set could be used, we conducted a careful comparison of graph readability factors through a hierarchical multiple regression analysis.
12
Zekaoui, Latifa. "Mixed covering arrays on graphs and tabu search algorithms." Thesis, University of Ottawa (Canada), 2006. http://hdl.handle.net/10393/27433.
Full textAbstract:
Covering arrays are combinatorial objects that have been successfully applied in the design of test suits for testing software, networks and circuits. Mixed covering arrays on graphs are new generalizations of both mixed covering arrays and covering arrays on graphs.
In this thesis, we give new theoretical results and constructions for mixed covering arrays on graphs. First, we extend to the mixed case the work done by Meagher and Stevens [31], which uses graph homomorphisms for covering arrays on graphs. Second, we study covering arrays on special classes of graphs. In particular, we solve to optimality the case in which G is a tree, a cycle or a bipartite graph, as well as give results for wheels and cubic graphs. We also provide general graph operations that preserve the size of a balanced covering array.
In the second part of the thesis, we do a complete experimental study of two tabu search algorithms for covering array construction. POT is a variation of the algorithm given by Stardom [40] while PAT is an implementation of the algorithm proposed by Nurmela [35]. We conclude that they provide effective methods for constructing covering arrays of moderate size. In particular, POT and PAT improve upper bounds for 18 sets of parameters for covering arrays.
13
Dusart, Jérémie. "Graph searches with applications to cocomparability graphs." Paris 7, 2014. http://www.theses.fr/2014PA077048.
Full textAbstract:
Un parcours de graphe est un mécanisme pour visiter de manière itérative les sommets d'un graphe. Cela a été une technique fondamentale dans la conception des algorithmes de graphe depuis les débuts de l'informatique. Bon nombre des premiers parcours étaient basées sur le parcours en largeur(BFS) ou en profondeur (DFS) et cela a donné des algorithmes efficaces pour les problèmes pratiques tels que la distance entre deux sommets, le diamètre, la connectivité, les problèmes de flot et la reconnaissance des graphes planaires. Le but de cette thèse est d'étudier les parcours de graphe Dans cette thèse, nous présentons des résultats généraux sur les parcours de graphe dans les graphes de cocomparabilité, mais aussi une nouvelle caractérisation des graphes de cocomparabilité et des applications des parcours de graphe pour résoudre le problème d'orientation transitive, de sous-graphe triangulé maximal, de clique séparatrice et de sommets simpliciaux. Un modèle simple et général est aussi présenté pour capturer la plupart des parcours de graphe<br>A graph search is a mechanism for systematically visiting the vertices of a graph. It has been a fundamental technique in the design of graph algorithms since the eraarly days of computer science. Many of the early search methods were based on Breadth First Search (BFS) or Depth First Search (DFS) and resulted in efficient algorithms for practical problems such as the distance between two vertices, diameter, connectivity, network flows and the recognition of planar graphs. The purpose of this thesis is to studied the graph search. In this thesis, we present general result about graph search in cocomparability grapj, but also a new charactrization of cocomparability graph and apllications of graph search to solve the problem of transitive orientation, maximal chordal subgraph, clique perator and simplicial vertices. A simple and general framework is also presented to capture most of the well known graph search
14
Tsalouchidou, Ioanna. "Temporal analysis of large dynamic graphs." Doctoral thesis, Universitat Pompeu Fabra, 2018. http://hdl.handle.net/10803/663755.
Full textAbstract:
The objective of this thesis is to provide a temporal analysis of the structural and interaction dynamics of large evolving graphs.
In this thesis we propose new definitions of important graph metrics in order to include the temporal dimension of the dynamic graphs.
We further extend the three important problems of data mining, in the temporal setting.
The three problems that we propose are temporal graph summarization, temporal community search and temporal betweenness centrality.
Additionally, we propose a distributed version of all our algorithms, that help our techniques to scale up to million vertices. We, finally, evaluate the validity of our methods in terms of efficiency and effectiveness with extensive experimentation on large-scale real-world graphs.<br>L’objectiu d’aquesta tesi és proporcionar una anàlisi temporal de l'evolució estructural i d’interacció de grans gràfics dinàmics.
En aquesta tesi proposem noves definicions de mètriques de gràfiques importants per tal d’incloure la dimensió temporal dels gràfics dinàmics.
Ampliem tres problemes importants de mineria de dades en gràfics per a un entorn temporal.
Els tres problemes són el resum de gràfics temporals, la cerca temporal de comunitats i la centralitat temporal dels gràfics.
A més, proposem una versió distribuïda de tots els nostres algoritmes, que ajuden a les nostres tècniques a escalar fins a milions de vèrtexs. Finalment, avaluem la validesa dels nostres mètodes en termes d’eficiència i eficàcia amb una àmplia experimentació en gràfics del món real a gran escala.<br>El objetivo de esta tesis es proporcionar un análisis temporal de las dinámicas estructurales y de interacción de grafos masivos dinámicos.
Para esto proponemos nuevas definiciones de métricas en grafos importantes para incluir la dimensión temporal de los grafos dinámicos.
Además, ampliamos tres problemas importantes de minería de datos en un contexto temporal.
Ellos son los resúmenes de grafos temporales, la búsqueda de comunidades en un contexto temporal y la centralidad temporal en grafos.
Además, proponemos una versión distribuida de todos nuestros algoritmos, que permiten que nuestras técnicas a escalar hasta millones de vértices. Finalmente, evaluamos la validez de nuestros métodos en términos de eficiencia y efectividad con extensos experimentos en gráfos de gran escala en el mundo real.
15
Owen, David R. "Random search of AND-OR graphs representing finite-state models." Morgantown, W. Va. : [West Virginia University Libraries], 2002. http://etd.wvu.edu/templates/showETD.cfm?recnum=2317.
Full textAbstract:
Thesis (M.S.)--West Virginia University, 2002.<br>Title from document title page. Document formatted into pages; contains vi, 96 p. : ill. Includes abstract. Includes bibliographical references (p. 91-96).
16
IZQUIERDO, YENIER TORRES. "KEYWORD SEARCH OVER FEDERATED RDF GRAPHS BY EXPLORING THEIR SCHEMAS." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2017. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=30739@1.
Full textAbstract:
PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO<br>CONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICO<br>O Resource Description Framework (RDF) foi adotado como uma recomendação do W3C em 1999 e hoje é um padrão para troca de dados na Web. De fato, uma grande quantidade de dados foi convertida em RDF, muitas vezes em vários conjuntos de dados fisicamente distribuídos ao longo de diferentes localizações. A linguagem de consulta SPARQL (sigla do inglês de SPARQL Protocol and RDF Query Language) foi oficialmente introduzido em 2008 para recuperar dados RDF e fornecer endpoints para consultar fontes distribuídas. Uma maneira alternativa de acessar conjuntos de dados RDF é usar consultas baseadas em palavras-chave, uma área que tem sido extensivamente pesquisada, com foco recente no conteúdo da Web. Esta dissertação descreve uma estratégia para compilar consultas baseadas em palavras-chave em consultas SPARQL federadas sobre conjuntos de dados RDF distribuídos, assumindo que cada conjunto de dados RDF tem um esquema e que a federação tem um esquema mediado. O processo de compilação da consulta SPARQL federada é explicado em detalhe, incluindo como computar o conjunto de joins externos entre as subconsultas locais geradas, como combinar, com a ajuda de cláusulas UNION, os resultados de consultas locais que não têm joins entre elas, e como construir a cláusula TARGET, de acordo com a composição da cláusula WHERE. Finalmente, a dissertação cobre experimentos com dados do mundo real para validar a implementação.<br>The Resource Description Framework (RDF) was adopted as a W3C recommendation in 1999 and today is a standard for exchanging data in the Web. Indeed, a large amount of data has been converted to RDF, often as multiple datasets physically distributed over different locations. The SPARQL Protocol and RDF Query Language (SPARQL) was officially introduced in 2008 to retrieve RDF datasets and provide endpoints to query distributed sources. An alternative way to access RDF datasets is to use keyword-based queries, an area that has been extensively researched, with a recent focus on Web content. This dissertation describes a strategy to compile keyword-based queries into federated SPARQL queries over distributed RDF datasets, under the assumption that each RDF dataset has a schema and that the federation has a mediated schema. The compilation process of the federated SPARQL query is explained in detail, including how to compute a set of external joins between the local subqueries, how to combine, with the help of the UNION clauses, the results of local queries which have no external joins between them, and how to construct the TARGET clause, according to the structure of the WHERE clause. Finally, the dissertation covers experiments with real-world data to validate the implementation.
17
Potamias, Michalis. "Indexing Distances in Large Graphs and Applications in Search Tasks." Boston University Computer Science Department, 2009. https://hdl.handle.net/2144/1721.
Full textAbstract:
This thesis elaborates on the problem of preprocessing a large graph so that single-pair shortest-path queries can be answered quickly at runtime. Computing shortest paths is a well studied problem, but exact algorithms do not scale well to real-world huge graphs in applications that require very short response time.
The focus is on approximate methods for distance estimation, in particular in landmarks-based distance indexing. This approach involves choosing some nodes as landmarks and computing (offline), for each node in the graph its embedding, i.e., the vector of its distances from all the landmarks. At runtime, when the distance between a pair of nodes is queried, it can be quickly estimated by combining the embeddings of the two nodes. Choosing optimal landmarks is shown to be hard and thus heuristic solutions are employed. Given a budget of memory for the index, which translates directly into a budget of landmarks, different landmark selection strategies can yield dramatically different results in terms of accuracy. A number of simple methods that scale well to large graphs are therefore developed and experimentally compared. The simplest methods choose central nodes of the graph, while the more elaborate ones select central nodes that are also far away from one another. The efficiency of the techniques presented in this thesis is tested experimentally using five different real world graphs with millions of edges; for a given accuracy, they require as much as 250 times less space than the current approach which considers selecting landmarks at random. Finally, they are applied in two important problems arising naturally in large-scale graphs, namely social search and community detection.
18
Mahalingam, Gayathri. "Connected domination in graphs." [Tampa, Fla.] : University of South Florida, 2005. http://purl.fcla.edu/fcla/etd/SFE0001225.
Full text
19
Newton, Matthew. "Sequential and parallel algorithms for low-crossing graph drawing." Thesis, Loughborough University, 2007. https://dspace.lboro.ac.uk/2134/12944.
Full textAbstract:
The one- and two-sided bipartite graph drawing problem alms to find a layout of a bipartite graph, with vertices of the two parts placed on parallel imaginary lines, that has the minimum number of edge-crossings. Vertices of one part are in fixed positions for the one-sided problem, whereas all vertices are free to move along their lines in the two-sided version. Many different heuristics exist for finding approximations to these problems, which are NP-hard. New sequential and parallel methods for producing drawings with low edgecrossings are investigated and compared to existing algorithms, notably Penalty Minimisation and Sifting, the current leaders. For the one-sided problem, new methods that include those based on simple stochastic hillclimbing, simulated annealing and genet.ic algorithms were tested. The new block-crossover genetic algorithm produced very good results with lower crossings than existing methods, although it tended to be slower. However, time was a secondary aim, the priority being to achieve low numbers of crossings. This algorithm can also be seeded with the output of an existing algorithm to improve results; combining with Penalty Minimisation in this way improved both the speed and number of crossings. Four parallel methods for the one-sided problem have been created, although two were abandoned because they gave bad results for even simple graphs. The other two methods, based on stochastic hill-climbing, produced acceptable results in faster times than similar sequential methods. PVM was used as the parallel communication system. Two new heuristics were studied for the two-sided problem, for which the only known existing method is to apply one-sided algorithms iteratively. The first is based on a heuristic for the linear arrangment problem; the second is a method of performing stochastic hill-climbing on two sides. A way of applying anyone-sided algorithm iteratively was also created. The linear arrangement method based on the Koren-Harel multi-scale algorithm achieved the best results, outperforming iterative Barycentre (previously the best method) and iterative Penalty Minimisation. Another area of this work created three new heuristics for the k-planar drawing problem where k > 1. These are the first known practical algorithms to solve this problem. A sequential genetic algorithm based on TimGA is devised to work on k-planar graphs. Two parallel algorithms, one island model and the other a 'mesh' model, are also given. Comparison of results for k = 2 indicate that the parallel island method is better than the other two methods. MPI was used for the parallel communication. Overall, 14 new methods are introduced, of which 10 were developed into working algorithms. For the one-sided bipartite graph drawing problem the new block-crossover genetic algorithm can produce drawings with lower crossings than the current best available algorithms. The parallel methods do not perform as well as the sequential ones, although they generally achieved the same results faster. All of the new two-sided methods worked well; the weighted two-sided swap stochastic hill-climbing method was comparable to the existing best method, iterative Barycentre, and generally produced drawings with lower crossings, although it suffered with needing a good termination condition. The new methods based on the linear arrangement problem consistently produced drawings with lower crossings than iterative Barycentre, although they were nearly always slower. A new parallel algorithm for the k-planar drawing problem, based on the island model, generally created drawings with the lowest edge-crossings, although no algorithms were known to exist to make comparisons.
20
CALLERSTRÖM, EMMA, and KAJSA ELFSTRÖM. "Multiprocessor Scheduling of Synchronous Data Flow Graphs using Local Search Algorithms." Thesis, KTH, Skolan för informations- och kommunikationsteknik (ICT), 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-166404.
Full textAbstract:
Design space exploration (DSE) is the process of exploring design alternatives before implementing real-time multiprocessor systems. One part of DSE is scheduling of the applications the system is developed for and to evaluate the performance to ensure that the real-time requirements are satisfied. Many real-time systems today use multiprocessors and finding the optimal schedule for an application on a multiprocessor system is known to be an NP-hard problem. Such an optimization problem can be time-consuming which justifies the use of heuristics. This thesis presents an approach for scheduling applications onto multiprocessors using local search algorithms. The applications are represented by SDF-graphs and the assumed platform has homogeneous processors without constraints regarding communication delays, memory consumption or buffer sizes. The goal of this thesis project was to investigate if heuristic search algorithms could find sufficiently good solutions in a reasonable amount of time. Experimental results show that local search algorithms have potential of contributing to DSE by finding high-performance schedules with reduced search time compared to algorithms trying to find the optimal scheduling solution.<br>Den process som föregår implementationen av ett realtidssystem där olika designalternativ utforskas kallas på engelska för Design space exploration (DSE). En del av DSE är att schemalägga de applikationer som systemet är avsett för och att utvärdera dess prestanda för att säkerställa att realtidskraven uppfylls. Många realtidssystem idag använder multiprocessorer och att hitta det optimala schemat för en applikation på ett multiprocessorsystem anses vara ett NP-svårt problem. Ett sådant optimeringsproblem är ofta tidskrävande vilket motiverar att använda en heuristik. Denna rapport presenterar ett tillvägagångssätt för schemaläggning av applikationer på multiprocessorer med hjälp av lokala sökalgoritmer. Applikationerna är representerade som SDF-grafer och plattformen antas ha homogena processorer utan restriktioner för bufferstorlek eller minnesåtgång och som kan kommunicera utan fördröjning. Målet med kandidatexamensarbetet var att undersöka om heuristiska sökalgoritmer kan hitta tillräckligt bra schemalösningar inom en rimlig söktid. Resultaten visar att lokala sökalgoritmer har potential att bidra till DSE genom att producera bra lösningar på kortare tid än algoritmer som söker den optimala lösningen.
21
Wiradee, Imrattanatrai. "Supporting Entity-oriented Search with Fine-grained Information in Knowledge Graphs." Kyoto University, 2020. http://hdl.handle.net/2433/259074.
Full text
22
Callerström, Emma, and Kajsa Elfström. "Multiprocessor Scheduling of Synchronous Data Flow Graphs using Local Search Algorithms." Thesis, KTH, Skolan för informations- och kommunikationsteknik (ICT), 2014. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-177144.
Full textAbstract:
Design space exploration (DSE) is the process of exploring design alternatives before implementing real-time multiprocessor systems. One part of DSE is scheduling of the applications the system is developed for and to evaluate the performance to ensure that the real-time requirements are satisfied. Many real-time systems today use multiprocessors and finding the optimal schedule for an application on a multiprocessor system is known to be an NP-hard problem. Such an optimization problem can be time-consuming which justifies the use of heuristics. This thesis presents an approach for scheduling applications onto multiprocessors using local search algorithms. The applications are represented by SDF-graphs and the assumed platform has homogeneous processors without constraints regarding communication delays, memory consumption or buffer sizes. The goal of this thesis project was to investigate if heuristic search algorithms could find sufficiently good solutions in a reasonable amount of time. Experimental results show that local search algorithms have potential of contributing to DSE by finding high-performance schedules with reduced search time compared to algorithms trying to find the optimal scheduling solution.
23
Kreslavskiy, Dmitry Michael. "Lorentz Lattice Gases on Graphs." Diss., Georgia Institute of Technology, 2003. http://hdl.handle.net/1853/6423.
Full textAbstract:
The present work consists of three parts. In the first part (chapters III and IV), the dynamics of Lorentz lattice gases (LLG) on graphs is analyzed. We study the fixed scatterer model on finite graphs. A tight bound is established on the size of the orbit for arbitrary graphs, and the model is shown to perform a depth-first search on trees. Rigidity models on trees are also considered, and the size of the resulting orbit is established. In the second part (chapter V), we give a complete description of dynamics for LLG on the one-dimensional integer lattice, with a particular interest in showing that these models are not capable of universal computation. Some statistical properties of these models are also analyzed. In the third part (chapter VI) we attempt to partition a pool of workers into teams that will function as independent TSS lines. Such partitioning may be aimed to make sure that all groups work at approximately the same rate. Alternatively, we may seek to maximize the rate of convergence of the corresponding dynamical systems to their fixed points with optimal production at the fastest rate. The first problem is shown to be NP-hard. For the second problem, a solution for splitting into pairs is given, and it is also shown that this solution is not valid for partitioning into teams composed of more than two workers.
24
Nabti, Chems Eddine. "Subgraph Isomorphism Search In Massive Graph Data." Thesis, Lyon, 2017. http://www.theses.fr/2017LYSE1293/document.
Full textAbstract:
L'interrogation de graphes de données est un problème fondamental qui connait un grand intérêt, en particulier pour les données structurées massives où les graphes constituent une alternative prometteuse aux bases de données relationnelles pour la modélisation des grandes masses de données. Cependant, l'interrogation des graphes de données est différente et plus complexe que l'interrogation des données relationnelles à base de tables. La tâche principale impliquée dans l'interrogation de graphes de données est la recherche d'isomorphisme de sous-graphes qui est un problème NP-complet.La recherche d'isomorphisme de sous-graphes est un problème très important impliqué dans divers domaines comme la reconnaissance de formes, l'analyse des réseaux sociaux, la biologie, etc. Il consiste à énumérer les sous-graphes d'un graphe de données qui correspondent à un graphe requête. Les solutions les plus connues de ce problème sont basées sur le retour arrière (backtracking). Elles explorent un grand espace de recherche, ce qui entraîne un coût de traitement élevé, notamment dans le cas de données massives.Pour réduire le temps et la complexité en espace mémoire dans la recherche d'isomorphisme de sous-graphes, nous proposons d'utiliser des graphes compressés. Dans notre approche, la recherche d'isomorphisme de sous-graphes est réalisée sur une représentation compressée des graphes sans les décompresser. La compression des graphes s'effectue en regroupant les sommets en super-sommets. Ce concept est connu dans la théorie des graphes par la décomposition modulaire. Il sert à générer une représentation en arbre d'un graphe qui met en évidence des groupes de sommets qui ont les mêmes voisins. Avec cette compression, nous obtenons une réduction substantielle de l'espace de recherche et par conséquent, une économie significative dans le temps de traitement.Nous proposons également une nouvelle représentation des sommets du graphe, qui simplifie le filtrage de l'espace de recherche. Ce nouveau mécanisme appelé compact neighborhood Index (CNI) encode l'information de voisinage autour d'un sommet en un seul entier. Cet encodage du voisinage réduit la complexité du temps de filtrage de cubique à quadratique. Ce qui est considérable pour les données massifs.Nous proposons également un algorithme de filtrage itératif qui repose sur les caractéristiques des CNIs pour assurer un élagage global de l'espace de recherche.Nous avons évalué nos approches sur plusieurs datasets et nous les avons comparées avec les algorithmes de l’état de l’art<br>Querying graph data is a fundamental problem that witnesses an increasing interest especially for massive structured data where graphs come as a promising alternative to relational databases for big data modeling. However, querying graph data is different and more complex than querying relational table-based data. The main task involved in querying graph data is subgraph isomorphism search which is an NP-complete problem. Subgraph isomorphism search, is an important problem which is involved in various domains such as pattern recognition, social network analysis, biology, etc. It consists to enumerate the subgraphs of a data graph that match a query graph. The most known solutions of this problem are backtracking-based. They explore a large search space which results in a high computational cost when we deal with massive graph data. To reduce time and memory space complexity of subgraph isomorphism search. We propose to use compressed graphs. In our approach, subgraph isomorphism search is achieved on compressed representations of graphs without decompressing them. Graph compression is performed by grouping vertices into super vertices. This concept is known, in graph theory, as modular decomposition. It is used to generate a tree representation of a graph that highlights groups of vertices that have the same neighbors. With this compression we obtain a substantial reduction of the search space and consequently a significant saving in the processing time. We also propose a novel encoding of vertices that simplifies the filtering of the search space. This new mechanism is called compact neighborhood Index (CNI). A CNI distills all the information around a vertex in a single integer. This simple neighborhood encoding reduces the time complexity of vertex filtering from cubic to quadratic which is considerable for big graphs. We propose also an iterative local global filtering algorithm that relies on the characteristics of CNIs to ensure a global pruning of the search space.We evaluated our approaches on several real-word datasets and compared them with the state of the art algorithms
25
Björklund, Henrik. "Combinatorial Optimization for Infinite Games on Graphs." Doctoral thesis, Uppsala University, Department of Information Technology, 2005. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-4751.
Full textAbstract:
<p>Games on graphs have become an indispensable tool in modern computer science. They provide powerful and expressive models for numerous phenomena and are extensively used in computer- aided verification, automata theory, logic, complexity theory, computational biology, etc.</p><p>The infinite games on finite graphs we study in this thesis have their primary applications in verification, but are also of fundamental importance from the complexity-theoretic point of view. They include parity, mean payoff, and simple stochastic games.</p><p>We focus on solving graph games by using iterative strategy improvement and methods from linear programming and combinatorial optimization. To this end we consider old strategy evaluation functions, construct new ones, and show how all of them, due to their structural similarities, fit into a unifying combinatorial framework. This allows us to employ randomized optimization methods from combinatorial linear programming to solve the games in expected subexponential time.</p><p>We introduce and study the concept of a controlled optimization problem, capturing the essential features of many graph games, and provide sufficent conditions for solvability of such problems in expected subexponential time.</p><p>The discrete strategy evaluation function for mean payoff games we derive from the new controlled longest-shortest path problem, leads to improvement algorithms that are considerably more efficient than the previously known ones, and also improves the efficiency of algorithms for parity games.</p><p>We also define the controlled linear programming problem, and show how the games are translated into this setting. Subclasses of the problem, more general than the games considered, are shown to belong to NP intersection coNP, or even to be solvable by subexponential algorithms.</p><p>Finally, we take the first steps in investigating the fixed-parameter complexity of parity, Rabin, Streett, and Muller games.</p>
26
Kellett, Matthew. "Black Hole Search in the Network and Subway Models." Thèse, Université d'Ottawa / University of Ottawa, 2012. http://hdl.handle.net/10393/20674.
Full textAbstract:
In this thesis we look at mobile agent solutions to black hole search and related problems. Mobile agents are computational entities that are autonomous, mobile, and can interact with their environment and each other. The black hole search problem is for a team of these agents to work together to map or explore a graph-like network environment where some elements of the network are dangerous to the agents. Most research into black hole search has focussed on finding a single dangerous node: a black hole. We look at the problem of finding multiple black holes and, in the case of dangerous graph exploration, multiple black links as well.
We look at the dangerous graph exploration problem in the network model. The network model is based on a normal static computer network modelled as a simple graph. We give an optimal solution to the dangerous graph exploration problem using agents that start scattered on nodes throughout the network. We then make the problem more difficult by allowing an adversary to delete links during the execution of the algorithm and provide a solution using scattered agents.
In the last decade or two, types of networks have emerged, such as ad hoc wireless networks, that are by their nature dynamic. These networks change quickly over time and can make distributed computations difficult. We look at black hole search in one type of dynamic network described by the subway model, which we base on urban subway systems. The model allows us to look at the cost of opportunistic movement by requiring the agents to move using carriers that follow routes among the network's sites, some of which are black holes. We show that there are basic limitations on any solution to black hole search in the subway model and prove lower bounds on any solution's complexity. We then provide two optimal solutions that differ in the agents' starting locations and how they communicate with one another.
Our results provide a small window into the cost of deterministic distributed computing in networks that have dynamic elements, but which are not fully random.
27
Lisena, Pasquale. "Knowledge-based music recommendation : models, algorithms and exploratory search." Electronic Thesis or Diss., Sorbonne université, 2019. http://www.theses.fr/2019SORUS614.
Full textAbstract:
Représenter l'information décrivant la musique est une activité complexe, qui implique différentes sous-tâches. Ce manuscrit de thèse porte principalement sur la musique classique et étudie comment représenter et exploiter ses informations. L'objectif principal est l'étude de stratégies de représentation et de découverte des connaissances appliquées à la musique classique, dans des domaines tels que la production de base de connaissances, la prédiction de métadonnées et les systèmes de recommandation. Nous proposons une architecture pour la gestion des métadonnées de musique à l'aide des technologies du Web Sémantique. Nous introduisons une ontologie spécialisée et un ensemble de vocabulaires contrôlés pour les différents concepts spécifiques à la musique. Ensuite, nous présentons une approche de conversion des données, afin d’aller au-delà de la pratique bibliothécaire actuellement utilisée, en s’appuyant sur des règles de mapping et sur l’interconnexion avec des vocabulaires contrôlés. Enfin, nous montrons comment ces données peuvent être exploitées. En particulier, nous étudions des approches basées sur des plongements calculés sur des métadonnées structurées, des titres et de la musique symbolique pour classer et recommander de la musique. Plusieurs applications de démonstration ont été réalisées pour tester les approches et les ressources précédentes<br>Representing the information about music is a complex activity that involves different sub-tasks. This thesis manuscript mostly focuses on classical music, researching how to represent and exploit its information. The main goal is the investigation of strategies of knowledge representation and discovery applied to classical music, involving subjects such as Knowledge-Base population, metadata prediction, and recommender systems. We propose a complete workflow for the management of music metadata using Semantic Web technologies. We introduce a specialised ontology and a set of controlled vocabularies for the different concepts specific to music. Then, we present an approach for converting data, in order to go beyond the librarian practice currently in use, relying on mapping rules and interlinking with controlled vocabularies. Finally, we show how these data can be exploited. In particular, we study approaches based on embeddings computed on structured metadata, titles, and symbolic music for ranking and recommending music. Several demo applications have been realised for testing the previous approaches and resources
28
RODRIGUES, DANILO MORET. "DISTRIBUTED RDF GRAPH KEYWORD SEARCH." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2013. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=23832@1.
Full textAbstract:
PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO<br>COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR<br>PROGRAMA DE SUPORTE À PÓS-GRADUAÇÃO DE INSTS. DE ENSINO<br>O objetivo desta dissertação é melhorar a busca por palavra-chave em
formato RDF. Propomos uma abordagem escalável, baseada numa representação
tensorial, que permite o armazenamento distribuído e, como consequência, o uso
de técnicas de paralelismo para agilizar a busca sobre grandes bases de RDF, em
particular, as publicadas como Linked Data. Um volume sem precedentes de
informação está sendo disponibilizado seguindo os princípios de Linked Data,
formando o que chamamos de Web of Data. Esta informação, tipicamente
codificada como triplas RDF, costuma ser representada como um grafo, onde
sujeitos e objetos são vértices, e predicados são arestas ligando os vértices. Em
consequência da ampla adoção de mecanismos de busca na World Wide Web,
usuários estão familiarizados com a busca por palavra-chave. No caso de grafos
RDF, no entanto, a extração de uma partição coerente de grafos para enriquecer os
resultados da busca é uma tarefa cara, demorada, e cuja expectativa do usuário é
de que seja executada em tempo real. Este trabalho tem como objetivo o
tratamento deste problema. Parte de uma solução proposta recentemente prega a
indexação do grafo RDF como uma matriz esparsa, que contém um conjunto de
informações pré-computadas para agilizar a extração de seções do grafo, e o uso
de consultas baseadas em tensores sobre a matriz esparsa. Esta abordagem
baseada em tensores permite que se tome vantagem de técnicas modernas de
programação distribuída, e.g., a utilização de bases de dados não-relacionais
fracionadas e o modelo de MapReduce. Nesta dissertação, propomos o desenho e
exploramos a viabilidade da abordagem baseada em tensores, com o objetivo de
construir um depósito de dados distribuído e agilizar a busca por palavras-chave
com uma abordagem paralela.<br>The goal of this dissertation is to improve RDF keyword search. We
propose a scalable approach, based on a tensor representation that allows for
distributed storage, and thus the use of parallel techniques to speed up the search
over large linked data sets, in particular those published as Linked Data. An
unprecedented amount of information is becoming available following the
principles of Linked Data, forming what is called the Web of Data. This
information, typically codified as RDF subject-predicate-object triples, is
commonly abstracted as a graph which subjects and objects are nodes, and
predicates are edges connecting them. As a consequence of the widespread
adoption of search engines on the World Wide Web, users are familiar with
keyword search. For RDF graphs, however, extracting a coherent subset of data
graphs to enrich search results is a time consuming and expensive task, and it is
expected to be executed on-the-fly at user prompt. The dissertation s goal is to
handle this problem. A recent proposal has been made to index RDF graphs as a
sparse matrix with the pre-computed information necessary for faster retrieval of
sub-graphs, and the use of tensor-based queries over the sparse matrix. The tensor
approach can leverage modern distributed computing techniques, e.g., nonrelational
database sharding and the MapReduce model. In this dissertation, we
propose a design and explore the viability of the tensor-based approach to build a
distributed datastore and speed up keyword search with a parallel approach.
29
Ratner, Michael. "Quantum Walks and Structured Searches on Free Groups and Networks." Diss., Temple University Libraries, 2017. http://cdm16002.contentdm.oclc.org/cdm/ref/collection/p245801coll10/id/442825.
Full textAbstract:
Mathematics<br>Ph.D.<br>Quantum walks have been utilized by many quantum algorithms which provide improved performance over their classical counterparts. Quantum search algorithms, the quantum analogues of spatial search algorithms, have been studied on a wide variety of structures. We study quantum walks and searches on the Cayley graphs of finitely-generated free groups. Return properties are analyzed via Green’s functions, and quantum searches are examined. Additionally, the stopping times and success rates of quantum searches on random networks are experimentally estimated.<br>Temple University--Theses
30
Klaus, Christian. "Probabilistic search on optimized graph topologies." Thesis, Monterey, California. Naval Postgraduate School, 2011. http://hdl.handle.net/10945/5569.
Full textAbstract:
Approved for public release; distribution is unlimited<br>This thesis investigates how the performance of a mobile searcher is affected by altering the search environment. We model the search environment as a simple connected, undirected graph. By adding new edges to the graph, we change the search environment. Our objective is to optimize search performance, that is, to minimize the (expected) time needed to find the target, in the context of probabilistic search. We first analyze two different methods to generate random connected graphs, then evaluate a number of methods to augment the graph, typically by considering the algebraic connectivity of the graph and its associated (Fiedler) eigenvector. Extensive simulation studies and resulting statistical and theoretical models show that adding a few wisely chosen edges to a sparse graph is sufficient to dramatically increase search performance. Further, we propose a novel method for incorporating prior information about the target's likely location by defining a subgraph on which the presented approach is performed, resulting in even greater improvements in search performance.
31
Yee, Ka-chi, and 余家智. "Keyword search on huge RDF graph." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2010. http://hub.hku.hk/bib/B46288478.
Full text
32
Bedrax-Weiss, Tania. "Optimal search protocols /." view abstract or download file of text, 1999. http://wwwlib.umi.com/cr/uoregon/fullcit?p9948016.
Full textAbstract:
Thesis (Ph. D.)--University of Oregon, 1999.<br>Typescript. Includes vita and abstract. Includes bibliographical references (leaves 206-211). Also available for download via the World Wide Web; free to University of Oregon users. Address: http://wwwlib.umi.com/cr/uoregon/fullcit?p9948016.
33
Rolland, Erik. "Abstract heuristic search methods for graph partitioning." Connect to resource, 1991. http://rave.ohiolink.edu/etdc/view.cgi?acc%5Fnum=osu1262633923.
Full text
34
Wang, Changliang. "Continuous subgraph pattern search over graph streams /." View abstract or full-text, 2009. http://library.ust.hk/cgi/db/thesis.pl?CSED%202009%20WANG.
Full text
35
Tanudjaja, Francisco 1978. "Using web graph structures to personalize search." Thesis, Massachusetts Institute of Technology, 2001. http://hdl.handle.net/1721.1/86737.
Full textAbstract:
Thesis (M.Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2001.<br>Includes bibliographical references (p. 93-97).<br>by Francisco Tanudjaja.<br>M.Eng.
36
Rolland, Eric. "Abstract heuristic search methods for graph partitioning." The Ohio State University, 1991. http://rave.ohiolink.edu/etdc/view?acc_num=osu1262633923.
Full text
37
Zou, Mengchuan. "Aspects of efficiency in selected problems of computation on large graphs." Thesis, Université de Paris (2019-....), 2019. http://www.theses.fr/2019UNIP7132.
Full textAbstract:
Cette thèse présente trois travaux liés à la conception d’algorithmes efficaces applicables à des graphes de grande taille. Dans le premier travail, nous nous plaçons dans le cadre du calcul centralisé, et ainsi la question de la généralisation des décompositions modulaires et de la conception d’un algorithme efficace pour ce problème. La décomposition modulaire et la détection de module, sont des moyens de révéler et d’analyser les propriétés modulaires de données structurées. Comme la décomposition modulaire classique est bien étudiée et possède un algorithme de temps linéaire optimal, nous étudions d’abord les généralisations de ces concepts en hypergraphes. C’est un sujet peu étudié mais qui permet de trouver de nouvelles structurations dans les familles de parties. Nous présentons ici des résultats positifs obtenus pour trois définitions de la décomposition modulaire dans les hypergraphes de la littérature. Nous considérons également la généralisation en permettant des erreurs dans les modules de graphes classiques et présentons des résultats négatifs pour deux telles définitions. Le deuxième travail est sur des requêtes de données dans un graphe. Ici, le modèle diffère des scénarios classiques dans le sens que nous ne concevons pas d’algorithmes pour résoudre un problème original, mais nous supposons qu’il existe un oracle fournissant des informations partielles sur la solution de problème initial, où les oracle ont une consommation de temps ou de ressources de requête que nous modélisons en tant que coûts, et nous avons besoin d’un algorithme décidant comment interroger efficacement l’oracle pour obtenir la solution exacte au problème initial. L’efficacité ici concerne le coût de la requête. Nous étudions un problème de la méthode de dichotomie généralisée pour lequel nous calculons une stratégie d’interrogation efficace afin de trouver une cible cachée dans le graphe. Nous présentons les résultats de nos travaux sur l’approximation de la stratégie optimale de recherche en dichotomie généralisée sur les arbres pondérés. Notre troisième travail est sur la question de l’efficacité de la mémoire. La configuration dans laquelle nous étudions sont des calculs distribués et avec la limitation en mémoire. Plus précisément, chaque nœud stocke ses données locales en échangeant des données par transmission de messages et est en mesure de procéder à des calculs locaux. Ceci est similaire au modèle LOCAL / CONGEST en calcul distribué, mais notre modèle requiert en outre que chaque nœud ne puisse stocker qu’un nombre constant de variables w.r.t. son degré. Ce modèle peut également décrire des algorithmes naturels. Nous implémentons une procédure existante de repondération multiplicative pour approximer le problème de flux maximal sur ce modèle. D’un point de vue méthodologique, les trois types d’efficacité que nous avons étudiées correspondent aux trois types de scénarios suivants: – Le premier est le plus classique. Considérant un problème, nous essayons de concevoir à la main l’algorithme le plus efficace. – Dans le second, l’efficacité est considérée comme un objectif. Nous modélisons les coûts de requête comme une fonction objectif, et utilisons des techniques d’algorithme d’approximation pour obtenir la conception d’une stratégie efficace. – Dans le troisième, l’efficacité est en fait posée comme une contrainte de mémoire et nous concevons un algorithme sous cette contrainte<br>This thesis presents three works on different aspects of efficiency of algorithm design for large scale graph computations. In the first work, we consider a setting of classical centralized computing, and we consider the question of generalizing modular decompositions and designing time efficient algorithm for this problem. Modular decomposition, and more broadly module detection, are ways to reveal and analyze modular properties in structured data. As the classical modular decomposition is well studied and have an optimal linear time algorithm, we firstly study the generalizations of these concepts to hypergraphs and present here positive results obtained for three definitions of modular decomposition in hypergraphs from the literature. We also consider the generalization of allowing errors in classical graph modules and present negative results for two this kind of definitions. The second work focuses on graph data query scenarios. Here the model differs from classical computing scenarios in that we are not designing algorithms to solve an original problem, but we assume that there is an oracle which provides partial information about the solution to the original problem, where oracle queries have time or resource consumption, which we model as costs, and we need to have an algorithm deciding how to efficiently query the oracle to get the exact solution to the original problem, thus here the efficiency is addressing to the query costs. We study the generalized binary search problem for which we compute an efficient query strategy to find a hidden target in graphs. We present the results of our work on approximating the optimal strategy of generalized binary search on weighted trees. Our third work draws attention to the question of memory efficiency. The setup in which we perform our computations is distributed and memory restricted. Specifically, every node stores its local data, exchanging data by message passing, and is able to proceed local computations. This is similar to the LOCAL/CONGEST model in distributed computing, but our model additionally requires that every node can only store a constant number of variables w.r.t. its degree. This model can also describe natural algorithms. We implement an existing procedure of multiplicative reweighting for approximating the maximum s–t flow problem on this model, this type of methodology may potentially provide new opportunities for the field of local or natural algorithms. From a methodological point of view, the three types of efficiency concerns correspond to the following types of scenarios: the first one is the most classical one given the problem, we try to design by hand the more efficient algorithm; the second one, the efficiency is regarded as an objective function .where we model query costs as an objective function, and using approximation algorithm techniques to get a good design of efficient strategy; the third one, the efficiency is in fact posed as a constraint of memory and we design algorithm under this constraint
38
Kinoshita, Yuji, Chiyomi Miyajima, Norihide Kitaoka, and Kazuya Takeda. "Spoken dialog strategy based on understanding graph search." IEEE, 2009. http://hdl.handle.net/2237/13900.
Full text
39
Zahrani, Mohammed Saeed. "Genetic local search algorithms for selected graph problems." Thesis, University of Hertfordshire, 2006. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.440188.
Full text
40
Dib, Fadi. "Improved neighbourhood search-based methods for graph layout." Thesis, University of Kent, 2018. https://kar.kent.ac.uk/69286/.
Full textAbstract:
Graph drawing, or the automatic layout of graphs, is a challenging problem. There are several search-based methods for graph drawing that are based on optimising a fitness function which is formed from a weighted sum of multiple criteria. This thesis proposes a new neighbourhood search-based method that uses a tabu search coupled with path relinking in order to optimise such fitness functions for general graph layouts with undirected straight lines. None of these methods have been previously used in general multi-criteria graph drawing. Tabu search uses a memory list to speed up searching by avoiding previously tested solutions, while the path relinking method generates new solutions by exploring paths that connect high quality solutions. We use path relinking periodically within the tabu search procedure to speed up the identification of good solutions. We have evaluated our new method against the commonly used neighbourhood search optimisation techniques: hill climbing and simulated annealing. Our evaluation examines the quality of the graph layout (fitness function's value) and the speed of the layout in terms of the number of the evaluated solutions required to draw a graph. We also examine the relative scalability of our method. Our experimental results were applied to both random graphs and a real-world dataset. We show that our method outperforms both hill climbing and simulated annealing by producing a better layout in a lower number of evaluated solutions. In addition, we demonstrate that our method has greater scalability as it can lay out larger graphs than the state-of-the-art neighbourhood search-based methods. Finally, we show that similar results can be produced in a real world setting by testing our method against a standard public graph dataset.
41
Wilson, Keith Eirik. "Factoring Semiprimes Using PG2N Prime Graph Multiagent Search." PDXScholar, 2011. https://pdxscholar.library.pdx.edu/open_access_etds/219.
Full textAbstract:
In this thesis a heuristic method for factoring semiprimes by multiagent depth-limited search of PG2N graphs is presented. An analysis of PG2N graph connectivity is used to generate heuristics for multiagent search. Further analysis is presented including the requirements on choosing prime numbers to generate 'hard' semiprimes; the lack of connectivity in PG1N graphs; the counts of spanning trees in PG2N graphs; the upper bound of a PG2N graph diameter and a conjecture on the frequency distribution of prime numbers on Hamming distance. We further demonstrated the feasibility of the HD2 breadth first search of PG2N graphs for factoring small semiprimes. We presented the performance of different multiagent search heuristics in PG2N graphs showing that the heuristic of most connected seedpick outperforms least connected or random connected seedpick heuristics on small PG2N graphs of size N
42
Okuno, Shingo. "Parallelization of Graph Mining using Backtrack Search Algorithm." 京都大学 (Kyoto University), 2017. http://hdl.handle.net/2433/225743.
Full text
43
Zhou, Rong. "Memory-efficient graph search applied to multiple sequence alignment." Diss., Mississippi State : Mississippi State University, 2005. http://library.msstate.edu/etd/show.asp?etd=etd-06282005-015428.
Full text
44
Krishnaswami, Sreedhar Bharathwaj. "Bayesian Optimization for Neural Architecture Search using Graph Kernels." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-291219.
Full textAbstract:
Neural architecture search is a popular method for automating architecture design. Bayesian optimization is a widely used approach for hyper-parameter optimization and can estimate a function with limited samples. However, Bayesian optimization methods are not preferred for architecture search as it expects vector inputs while graphs are high dimensional data. This thesis presents a Bayesian approach with Gaussian priors that use graph kernels specifically targeted to work in the higherdimensional graph space. We implemented three different graph kernels and show that on the NAS-Bench-101 dataset, an untrained graph convolutional network kernel outperforms previous methods significantly in terms of the best network found and the number of samples required to find it. We follow the AutoML guidelines to make this work reproducible.<br>Neural arkitektur sökning är en populär metod för att automatisera arkitektur design. Bayesian-optimering är ett vanligt tillvägagångssätt för optimering av hyperparameter och kan uppskatta en funktion med begränsade prover. Bayesianska optimeringsmetoder är dock inte att föredra för arkitektonisk sökning eftersom vektoringångar förväntas medan grafer är högdimensionella data. Denna avhandling presenterar ett Bayesiansk tillvägagångssätt med gaussiska prior som använder grafkärnor som är särskilt fokuserade på att arbeta i det högre dimensionella grafutrymmet. Vi implementerade tre olika grafkärnor och visar att det på NASBench- 101-data, till och med en otränad Grafkonvolutionsnätverk-kärna, överträffar tidigare metoder när det gäller det bästa nätverket som hittats och antalet prover som krävs för att hitta det. Vi följer AutoML-riktlinjerna för att göra detta arbete reproducerbart.
45
Cui, Chen. "MRI fat-water separation using graph search based methods." Diss., University of Iowa, 2017. https://ir.uiowa.edu/etd/5740.
Full textAbstract:
The separation of water and fat from multi-echo images is a classic problem in magnetic resonance imaging (MRI) with a wide range of important clinical applications. For example, removal of fat signal can provide better visualization of other signal of interest in MRI scans. In other cases, the fat distribution map can be of great importance in diagnosis.
Although many methods have been proposed over the past three decades, robust fat water separation remains a challenge as radiological technology and clinical expectation continue to grow. The problem presents three key difficulties: a) the presence of B0 field inhomogeneities, often large in the state-of-the-art research and clinical settings, which makes the problem non-linear and ill-posed; b) the ambiguity of signal modeling in locations with only one metabolite (either fat or water), which can manifest as spurious fat water swaps in the separation; c) the computational expenditure in fat water separation as the size of the data is increasing along with evolving MRI hardware, which hampers the clinical applicability of the fat water separation.
The main focus of this thesis is to develop novel graph based algorithms to estimate the B0 field inhomogeneity maps and separate fat water signals with global accuracy and computational efficiency. We propose a new smoothness constrained framework for the GlObally Optimal Surface Estimation (GOOSE), in which the spatial smoothness of the B0 field is modeled as a finite constraint between adjacent voxels in a uniformly discretized graph. We further develop a new non-equidistant graph model that enables a Rapid GlObally Optimal Surface Estimation (R-GOOSE) in a subset of the fully discretized graph in GOOSE. Extensions of the above frameworks are also developed to achieve high computational efficiency for processing large 3D datasets. Global convergence of the optimization formulation is proven in all frameworks. The developed methods have also been extensively compared to the existing state-of-the-art fat water separation methods on a variety of datasets with consistent performance of high accuracy and efficiency.
46
Soto, Manuel. "Unmanned aerial vehicle real-time guidance system via state space heuristic search." To access this resource online via ProQuest Dissertations and Theses @ UTEP, 2007. http://0-proquest.umi.com.lib.utep.edu/login?COPT=REJTPTU0YmImSU5UPTAmVkVSPTI=&clientId=2515.
Full text
47
Sugiura, Shin-ichi, Takeshi Furuhashi, Tomohiro Yoshikawa, and Bo Hao. "A Study on Disease Search Support System using HK Graph." 日本知能情報ファジィ学会, 2008. http://hdl.handle.net/2237/20679.
Full textAbstract:
Session ID: SU-G2-4<br>Joint 4th International Conference on Soft Computing and Intelligent Systems and 9th International Symposium on advanced Intelligent Systems, September 17-21, 2008, Nagoya University, Nagoya, Japan
48
Wang, Hongjian. "Cellular matrix for parallel k-means and local search to Euclidean grid matching." Thesis, Belfort-Montbéliard, 2015. http://www.theses.fr/2015BELF0280/document.
Full textAbstract:
Dans cette thèse, nous proposons un modèle de calcul parallèle, appelé « matrice cellulaire », pour apporter des réponses aux problématiques de calcul parallèle appliqué à la résolution de problèmes d’appariement de graphes euclidiens. Ces problèmes d’optimisation NP-difficiles font intervenir des données réparties dans le plan et des structures élastiques représentées par des graphes qui doivent s’apparier aux données. Ils recouvrent des problèmes connus sous des appellations diverses telles que geometric k-means, elastic net, topographic mapping, elastic image matching. Ils permettent de modéliser par exemple le problème du voyageur de commerce euclidien, le problème du cycle médian, ainsi que des problèmes de mise en correspondance d’images. La contribution présentée est divisée en trois parties. Dans la première partie, nous présentons le modèle de matrice cellulaire qui partitionne les données et définit le niveau de granularité du calcul parallèle. Nous présentons une boucle générique de calcul parallèle qui modélise le principe des projections de graphes et de leur appariement. Dans la deuxième partie, nous appliquons le modèle de calcul parallèle aux algorithmes de k-means avec topologie dans le plan. Les algorithmes proposés sont appliqués au voyageur de commerce, à la génération de maillage structuré et à la segmentation d'image suivant le concept de superpixel. L’approche est nommée superpixel adaptive segmentation map (SPASM). Dans la troisième partie, nous proposons un algorithme de recherche locale parallèle, appelé distributed local search (DLS). La solution du problème résulte des opérations locales sur les structures et les données réparties dans le plan, incluant des évaluations, des recherches de voisinage, et des mouvements structurés. L’algorithme est appliqué à des problèmes d’appariement de graphe tels que le stéréo-matching et le problème de flot optique<br>In this thesis, we propose a parallel computing model, called cellular matrix, to provide answers to problematic issues of parallel computation when applied to Euclidean graph matching problems. These NP-hard optimization problems involve data distributed in the plane and elastic structures represented by graphs that must match the data. They include problems known under various names, such as geometric k-means, elastic net, topographic mapping, and elastic image matching. The Euclidean traveling salesman problem (TSP), the median cycle problem, and the image matching problem are also examples that can be modeled by graph matching. The contribution presented is divided into three parts. In the first part, we present the cellular matrix model that partitions data and defines the level of granularity of parallel computation. We present a generic loop for parallel computations, and this loop models the projection between graphs and their matching. In the second part, we apply the parallel computing model to k-means algorithms in the plane extended with topology. The proposed algorithms are applied to the TSP, structured mesh generation, and image segmentation following the concept of superpixel. The approach is called superpixel adaptive segmentation map (SPASM). In the third part, we propose a parallel local search algorithm, called distributed local search (DLS). The solution results from the many local operations, including local evaluation, neighborhood search, and structured move, performed on the distributed data in the plane. The algorithm is applied to Euclidean graph matching problems including stereo matching and optical flow
49
Bourneuf, Lucas. "A search space of graph motifs for graph compression : from Powergraphs to triplet concepts." Thesis, Rennes 1, 2019. http://www.theses.fr/2019REN1S060.
Full textAbstract:
L'Analyse Power Graph est une technique de compression sans perte de graphe visant à réduire la complexité visuelle d'un graphe. Le processus consiste à détecter des motifs, les cliques et les bicliques, qui permettent d'établir des groupes de nœuds organisés hiérarchiquement, des groupes d'arcs, et finalement un graphe réduit à ces groupes. Cette thèse propose tout d'abord la formalisation de l'espace de recherche de l'Analyse Power Graph, en utilisant l'Analyse de Concepts Formels comme base théorique pour exprimer le processus de compression. Le traitement indépendant de deux motifs présente des difficultés et nous proposons une notion unificatrice, les concepts triplets, qui conduiront à un motif unique plus général pour la compression. L'Analyse Power Graph et la nouvelle approche ont été implémentés dans un formalisme logique de Programmation par Ensembles Réponses (ASP), et nous présentons quelques applications en bioinformatique pour les deux approches. La thèse se clôt sur la présentation d'un environnement de visualisation et de spécification de haut-niveau en théorie des graphes<br>Power Graph Analysis is a lossless graph compression method aiming at reducing the visual complexity of a graph. The process is to detect motifs, cliques and bicliques, which enables the hierarchical clustering of nodes, the grouping of edges, and ultimately a graph reduced to these groups. This thesis exposes first the formalization of the Power Graph Analysis search space, using Formal Concept Analysis as a theoretical ground to express the compression process. Because the independent treatment of two motifs presents some caveats, we propose a unification framework, triplet concepts, which encode a more general motif for compression. Both Power Graph Analysis and the new approach have been implemented in Answer Set Programming (ASP), a logical formalism, and we present some applications in bioinformatics of these two approaches. This thesis ends on the presentation of an high-level specification and visualization environment for graph theory
50
Tfaili, Sara. "Contribution aux graphes creux pour le problème de tournées sur arcs déterministe et robustes : théorie et algorithmes." Thesis, Normandie, 2017. http://www.theses.fr/2017NORMLH14/document.
Full textAbstract:
Cette thèse comporte deux parties majeures : la première partie est dédiée à l'étude du problème sparse CARP déterministe où nous avons développé une transformation du sparse CARP en un sparse CVRP. La seconde est consacrée au problème sparse CARP avec coûts sous incertitude. Nous avons donné une formulation mathématique du problème en min-max. Cette modélisation a permis d'identifier le pire scénario pour le problème robuste. Deux approches algorithmiques ont été proposées pour une résolution approchée<br>This dissertation consists of two main parts : in the first part, we study the detreministic capacitated arc routing problem over sparse underlying graphs wher we have developed a new transformation techniquevof sparse CARP into sparse CVRP. The second part is consecrated about the sparse CARP with travel costs uncertainty. We have given a mathematical formulation of the probleme in min-max. A worst scenario for the robust problem is then identified, and two algorithmic approaches are proposed to determine a solution of the studied problem