Throughout the 1990s ADHD diagnosis and medication rates have increased rapidly, and this trend continues today. These sharp increases have been met with both public and clinical criticism, detractors stating over-diagnosis is a problem and healthy children are being unnecessarily medicated and labeled as disabled. However, others say that ADHD is being under-diagnosed in some populations. Critics often state that there are multiple factors that introduce subjectivity into the diagnosis process, meaning that a final diagnosis may be influenced by more than the desire to protect a patient's wellbeing. Some of these factors include standardized testing, legislation affecting special education funding, and the diagnostic process. In an effort to circumvent these extraneous factors, this work aims to further develop a potential method of using EEG signals to accurately discriminate between ADHD and non-ADHD children using features that capture spectral and perhaps temporal information from evoked EEG signals. KNN has been shown in prior research to be an effective tool in discriminating between ADHD and non-ADHD, therefore several different KNN models are created using features derived in a variety of fashions. One takes into account the heterogeneity of ADHD, and another one seeks to exploit differences in executive functioning of ADHD and non-ADHD subjects. The results of this classification method vary widely depending on the sample used to train and test the KNN model. With unfiltered Dataset 1 data over the entire ANT1 period, the most accurate EEG channel pair achieved an overall vector classification accuracy of 94%, and the 5th percentile of classification confidence was 80%. These metrics suggest that using KNN of EEG signals taken during the ANT task would be a useful diagnosis tool. However, the most accurate channel pair for unfiltered Dataset 2 data achieved an overall accuracy of 65% and a 5th percentile of classification confidence of 17%. The same method that worked so well for Dataset 1 did not work well for Dataset 2, and no conclusive reason for this difference was identified, although several methods to remove possible sources of noise were used. Using target time linked intervals did appear to marginally improve results in both Dataset 1 and Dataset 2. However, the changes in accuracy of intervals relative to target presentation vary between Dataset 1 and Dataset 2. Separating subjects into heterogeneity classes does appear to result in good (up to 83%) classification accuracy for some classes, but results are poor (about 50%) for other heterogeneity classes. A much larger data set is necessary to determine whether or not the very positive results found with Dataset 1 extend to a wide population. / Master of Science / Throughout the 1990s ADHD diagnosis and medication rates have increased rapidly, and this trend continues today. These sharp increases have been met with both public and clinical criticism, detractors stating over-diagnosis is a problem and healthy children are being unnecessarily medicated and labeled as disabled. However, others say that ADHD is being underdiagnosed in some populations. Critics often state that there are multiple factors that introduce subjectivity into the diagnosis process, meaning that a final diagnosis may be influenced by more than the desire to protect a patient’s wellbeing. Some of these factors include standardized testing, legislation affecting special education funding, and the diagnostic process. In an effort to circumvent these extraneous factors, this work aims to further develop a potential method of using EEG signals to accurately discriminate between ADHD and non-ADHD children using features that capture spectral and perhaps temporal information from evoked EEG signals. KNN has been shown in prior research to be an effective tool in discriminating between ADHD and non-ADHD, therefore several different machine learning models are created using features derived in a variety of fashions. One takes into account the heterogeneity of ADHD, and another one seeks to exploit differences in executive functioning of ADHD and non-ADHD subjects. The results of this classification method vary widely depending on the sample used to train and test the KNN model, classification accuracy has ranged from 65% to 94%, and the cause for this variation was not identified. A much larger data set is necessary to determine whether or not the very positive results found with Dataset 1 extend to a wide population.

This thesis presents the development and implementation of a machine learning prediction model for concurrently aggregating interval linear step distance predictions before future foot placement. Specifically, on-body inertial measurement units consisting of accelerometers, gyroscopes, and magnetometers, through integrated development by Xsens, are used for measuring human walking behavior in real-time. The data collection process involves measuring activity from two subject participants who travel an intended course consisting of flat, stair, and sloped walking elements. This work discusses the formulation of the ensemble machine learning prediction algorithm, real-time application design considerations, feature extraction and selection, and experimental testing under which this system performed several different test case conditions. It was found that the system was able to predict the linear step distances for 47.2% of 1060 steps within 7.6cm accuracy, 67.5% of 1060 steps within 15.2cm accuracy, and 75.8% of 1060 steps within 23cm. For separated flat walking, it was found that 93% of the 1060 steps have less than 25% error, and 75% of the 1060 steps have less than 10% error which is an improvement over the commingled data set. Future applications and work to expand upon from this system are discussed for improving the results discovered from this work. / Master of Science / This thesis presents the development and implementation of a machine learning prediction model for determining the stepping distance of future steps in real-time walking before their placement occurs. Specialized sensor units for measuring human motion activity are worn on the body for collecting and characterizing human walking behavior in real-time. Two subject participants are asked to walk a planned course consisting of flat, stair, and sloped walking elements. This work discusses the prediction algorithm voting scheme, real-time application design considerations, descriptive data elements for the algorithm, and experimental testing under which this system performed several different test case conditions. Detailed experimental tests are concluded in order to fully understand the extent of the system’s performance and the behaviors it exhibits throughout. The approach explored in this work enables researchers and roboticists to develop improvements and construct variations which may become superior to this method.

As of 2016, diagnosis of ADHD in the US is controversial. Diagnosis of ADHD is based on subjective observations, and treatment is usually done through stimulants, which can have negative side-effects in the long term. Evidence shows that the probability of diagnosing a child with ADHD not only depends on the observations of parents, teachers, and behavioral scientists, but also on state-level special education policies. In light of these facts, unbiased, quantitative methods are needed for the diagnosis of ADHD. This problem has been tackled since the 1990s, and has resulted in methods that have not made it past the research stage and methods for which claimed performance could not be reproduced. This work proposes a combination of machine learning algorithms and signal processing techniques applied to EEG data in order to classify subjects with and without ADHD with high accuracy and confidence. More specifically, the K-nearest Neighbor algorithm and Gaussian-Mixture-Model-based Universal Background Models (GMM-UBM), along with autoregressive (AR) model features, are investigated and evaluated for the classification problem at hand. In this effort, classical KNN and GMM-UBM were also modified in order to account for uncertainty in diagnoses. Some of the major findings reported in this work include classification performance as high, if not higher, than those of the highest performing algorithms found in the literature. One of the major findings reported here is that activities that require attention help the discrimination of ADHD and Non-ADHD subjects. Mixing in EEG data from periods of rest or during eyes closed leads to loss of classification performance, to the point of approximating guessing when only resting EEG data is used. / Master of Science / As of 2016, diagnosis of ADHD in the US is controversial. Diagnosis of ADHD is based on subjective observations, and treatment is usually done through stimulants, which can have negative side-effects in the long term. Evidence shows that the probability of diagnosing a child with ADHD not only depends on the observations of parents, teachers, and behavioral scientists, but also on state-level special education policies. In light of these facts, unbiased, quantitative methods are needed for the diagnosis of ADHD. This problem has been tackled since the 1990s, and has resulted in methods that have not made it past the research stage and methods for which claimed performance could not be reproduced. This work proposes a combination of machine learning algorithms and signal processing techniques applied to EEG data in order to classify subjects with and without ADHD with high accuracy and confidence. Signal processing techniques are used to extract autoregressive (AR) coefficients, which contain information about brain activities and are used as “features”. Then, the features, extracted from datasets containing ADHD and Non-ADHD subjects, are used to create or train models that can classify subjects as either ADHD or Non-ADHD. Lastly, the models are tested using datasets that are different from the ones used in the previous stage, and performance is analyzed based on how many of the predicted labels (ADHD or Non-ADHD) match the expected labels. Some of the major findings reported in this work include classification performance as high, if not higher, than those of the highest performing algorithms found in the literature. One of the major findings reported here is that activities that require attention help the discrimination of ADHD and Non-ADHD subjects. Mixing in EEG data from periods of rest or during eyes closed leads to loss of classification performance, to the point of approximating guessing when only resting EEG data is used.

La classification des images est aujourd'hui un défi d'une grande ampleur puisque ça concerne d’un côté les millions voir des milliards d'images qui se trouvent partout sur le web et d’autre part des images pour des applications temps réel critiques. Cette classification fait appel en général à des méthodes d'apprentissage et à des classifieurs qui doivent répondre à la fois à la précision ainsi qu'à la rapidité. Ces problèmes d'apprentissage touchent aujourd'hui un grand nombre de domaines d'applications: à savoir, le web (profiling, ciblage, réseaux sociaux, moteurs de recherche), les "Big Data" et bien évidemment la vision par ordinateur tel que la reconnaissance d'objets et la classification des images. La présente thèse se situe dans cette dernière catégorie et présente des algorithmes d'apprentissage supervisé basés sur la minimisation de fonctions de perte (erreur) dites "calibrées" pour deux types de classifieurs: k-Plus Proches voisins (kNN) et classifieurs linéaires. Ces méthodes d'apprentissage ont été testées sur de grandes bases d'images et appliquées par la suite à des images biomédicales. Ainsi, cette thèse reformule dans une première étape un algorithme de Boosting des kNN et présente ensuite une deuxième méthode d'apprentissage de ces classifieurs NN mais avec une approche de descente de Newton pour une convergence plus rapide. Dans une seconde partie, cette thèse introduit un nouvel algorithme d'apprentissage par descente stochastique de Newton pour les classifieurs linéaires connus pour leur simplicité et leur rapidité de calcul. Enfin, ces trois méthodes ont été utilisées dans une application médicale qui concerne la classification de cellules en biologie et en pathologie. / Image classification becomes a big challenge since it concerns on the one hand millions or billions of images that are available on the web and on the other hand images used for critical real-time applications. This classification involves in general learning methods and classifiers that must require both precision as well as speed performance. These learning problems concern a large number of application areas: namely, web applications (profiling, targeting, social networks, search engines), "Big Data" and of course computer vision such as the object recognition and image classification. This thesis concerns the last category of applications and is about supervised learning algorithms based on the minimization of loss functions (error) called "calibrated" for two kinds of classifiers: k-Nearest Neighbours (kNN) and linear classifiers. Those learning methods have been tested on large databases of images and then applied to biomedical images. In a first step, this thesis revisited a Boosting kNN algorithm for large scale classification. Then, we introduced a new method of learning these NN classifiers using a Newton descent approach for a faster convergence. In a second part, this thesis introduces a new learning algorithm based on stochastic Newton descent for linear classifiers known for their simplicity and their speed of convergence. Finally, these three methods have been used in a medical application regarding the classification of cells in biology and pathology.

O operador de Junção é um operador importante da Álgebra Relacional que combina os pares de tuplas que atendem a uma dada condição de comparação entre os valores dos atributos de duas relações. Quando a comparação avalia a similaridade entre pares de valores, o operador é chamado Junção por Similaridade. Esse operador tem aplicações em diversos contextos, tais como o suporte de tarefas de mineração e análise de dados em geral, e a detecção de quase-duplicatas, limpeza de dados e casamento de cadeias de caracteres em especial. Dentre os operadores de junção por similaridade existentes, a Junção por Abrangência (range join) é a mais explorada na literatura. Contudo, ela apresenta limitações, tal como a dificuldade para se encontrar um limiar de similaridade adequado. Nesse contexto, a Junção por k-vizinhos mais próximos (knearest neighbor join kNN join) é considerada mais intuitiva, e portanto mais útil que o range join. Entretanto, executar um kNN join é computacionalmente mais caro, o que demanda por abordagens baseadas na técnica de laço aninhado, e as técnicas existentes para a otimização do algoritmo são restritas a um domínio de dados em particular. Visando agilizar e generalizar a execução do kNN join, a primeira contribuição desta tese foi o desenvolvimento do algoritmo QuickNearest, baseado na técnica de divisão e conquista, que é independente do domínio dos dados, independente da função de distância utilizada, e que computa kNNjoins de maneira muito eficiente. Os experimentos realizados apontam que o QuickNearest chega a ser 4 ordens de magnitude mais rápido que os métodos atuais. Além disso, o uso de operadores de junção por similaridade em ambientes relacionais é problemático, principalmente por dois motivos: (i)emgeral o resultado tem cardinalidade muito maior do que o realmente necessário ou esperado pela maioria das aplicações de análise de dados; e (ii) as consultas que os utilizam envolvem também operações de ordenação, embora a ordem seja um conceito não associado à teoria relacional. A segunda contribuição da tese aborda esses dois problemas, tratando os operadores de junção por similaridade existentes como casos particulares de um conjunto mais amplo de operadores binários, para o qual foi definido o conceito de Wide-joins. Os operadores wide-joins recuperam os pares mais similares em geral e incorporam a ordenação como uma operação interna ao processamento, de forma compatível com a teoria relacional e que permite restringir a cardinalidade dos resultados a tuplas de maior interesse para as aplicações. Os experimentos realizados mostram que os wide-joins são rápidos o suficiente para serem usados em aplicações reais, retornam resultados de qualidade melhor do que os métodos concorrentes e são mais adequados para execução num ambiente relacional do que os operadores de junção por similaridade tradicionais. / Joins are important Relational Algebra operators. They pair tuples from two relations that meet a given comparison condition between the attribute values. When the evaluation compares the similarity among the values, the operator is called a Similarity Join. This operator has application to a variety of contexts, such as supporting data mining tasks and data analysis in general, and near-duplicate detection, data cleaning and string matching in particular. Among the existing types of similarity joins, the range join is the most explored one in the literature. However, it has several shortcomings, such as the diculty to find adequate similarity thresholds. In such context, the k-nearest neighbors join (kNN join) is considered more intuitive, and therefore more useful than the range join. However, the kNN join execution is computationally well more expensive, thus demanding implementations either based on nested loop techniques, which are generic, or on optimizing techniques but that are specific data given domains. In order to accelerate and generalize kNN join execution, the first contribution of this thesis was the development of the QuickNearest algorithm, based on the divide and conquest approach that is independent of the data domain, independent of the distance function used, and that computes kNN joins very eciently. Experiments performed with the QuickNearest algorithm show that it is up to four orders of magnitude faster than current methods. Nevertheless, using similarity join operators in relational environments remains generally troublesome, due to two main reasons: (i) the result often has a cardinality much larger than what is actually needed or expected by most of the data analysis applications; and (ii) queries that use them almost always also require sorting operations, but order concept is not present in the relational theory. The second contribution of the thesis addresses these two problems through the definition of the concept of Wide-joins, which turns the existing similarity join operators just as particular cases of a more powerful set of binary operators. Awide-join operator retrieves the pairs most similar in general and already incorporates ordering as an internal operation to its processing, what makes it fully compatible with the relational theory. The concept also provides powerful ways to restrict the result cardinality just to tuples really meaningful for the applications. In fact, the experiments have also shown that wide-joins are fast enough to be useful for real applications, they return results of better quality than competing methods, and are more suitable for execution in a relational environment than the traditional similarity join operators.

台灣股票市場屬於淺碟型，因此外界的訊息易於影響股價波動；同時台灣是一個以個別投資人為主的散戶市場，外界的訊息會影響市場投資。因此，重大訊息的發布對公司股價變化的影響，值得我們進一步探討。 本研究以公開資訊觀測站之重大訊息為資料來源，蒐集2005~2009年間統一、中華電信、長榮航空以及臺灣企銀四間上市公司之重大訊息共1382篇。利用文字探勘kNN演算法將四間公司之重大訊息加以分群，分析出各訊息的發布對於股價之影響程度，並找出不同群組之重大訊息的漲跌趨勢，期能對未來即時重大訊息的發布，分析出其對於股價之漲跌影響，進一步得到訊息發布日後兩日之報酬率走勢，成為日後投資標的之選擇參考。 本研究結果顯示取樣公司於發布前兩日至發布後兩日，交易量有顯著之異常，顯示訊息發布對於公司股票確有影響；而不同的重大訊息內容，將會被分於不同之群組當中，各群組也各有其不同之漲跌趨勢，本研究於測試資料之分類結果，整體平均有六成五之準確率，在於上漲類別之準確率更高達八成；最後於發布後累積報酬率之影響，投資正確率平均高於六成。 本研究透過系統化之分析與預測，省去投資者對於重大訊息之搜尋以及解讀的時間，提供投資者一個可供參考之依據。 / In this study we used the technique of text mining to classify the material information of companies and analyze how the disclosure of it affects the market. Hence, we would be able to predict the price of stock based on disclosures of the material information and then use the outcome as reference of investment. This study chose the Market Observation Post System as the source of information to its justice. We chose UNI-PRESIDENT ENTERPRISES CORP, Chunghwa Telecom Co., Ltd, EVA AIRWAYS CORPORATION and Taiwan Business Bank for their great evaluation of the information disclosure. We collected 1382 material information from 2005 to 2009 and for the better performance, we selected kNN algorithm as our rule of classification. We conducted three experiments in this study. In these experiments, we have approved that the trading volume of two periods were with significant differences. We have over 60% accuracy of the all data to classify the tested data. As a result, we found that the return rate of the “up” group has over 60% upside probability and the “down” group has over 60% downside probability. In this study, we built a time-saving automatic system to group material information and find out those that are valuable. Based on our result, we provided a reference to investors for their investment strategy. At the same time, we also came up with some inspiration for future research.

Cette thèse vise à trouver des approches possibles pour l’amélioration des propriétés électromécaniques de monocristaux piézoélectriques à base de KNN. La TSSG et la SSSG sont entreprises afin de faire croître des monocristaux La conclusion de l'aspect de croissance cristalline est: (1) Pour chaque élément pris individuellement, leurs coefficients de ségrégation reposent fortement sur leurs concentrations initiales dans la solution liquide. (2) La compétition entre éléments occupant le même site du réseau est démontrée. (3) Le très faible coefficient de ségrégation de Li dans la matrice KNN est responsable de l'apparition d'une phase secondaire présentant la structure bronze de tungstène quadratique. (4) Les régions optiquement laiteuses observées dans les monocristaux diminuent la réponse électrique et peuvent être réduites par traitement thermique et refroidissement lent. Dans la deuxième partie, nous avons utilisé trois approches pour améliorer le comportement piézo/ferroélectrique des monocristaux à base de KNN. La Ta ou Sb substitution indique qu'une réponse électromécanique améliorée est obtenue lorsque la transition orthorhombique-quadratique est à proximité de la température ambiante. Le traitement thermique sous atmosphère d'O2 pur a conduit au doublement de la valeur du coefficient piézoélectrique et des paramètres ferroélectriques d'un monocristal de (K,Na,Li) (Ta,Nb,Sb)O3. Son coefficient piézoélectrique à la température ambiante, qui constitue un record mondial à l’heure actuelle vis-à-vis de ce qui est reporté dans la littérature internationale, vaut 732 pC/N. La troisième approche consiste au dopage des monocristaux de (K,Na,Li)(Ta,Nb)O3 avec Mn. / The thesis aims to find possible approaches for improved electromechanical properties in KNN-based piezoelectric single crystals. Both submerged-seed and top-seeded solution growth techniques were employed to produce single crystals. Conclusions from the crystal growth aspect are: (i) For individual elements, segregation coefficients highly rely on the initial concentration in the liquid solution. (ii) A competition between elements occupied on the same lattice site was found. (iii) The very low Li segregation coefficient in the KNN matrix is responsible for the occurrence of a secondary phase with the tetragonal tungsten bronze structure. (iv) Observed optically-cloudy regions in as-grown crystals decrease the electrical response and can be reduced by thermal treatment with slow cooling. In the second part, we used three approaches to enhance the piezoelectric and ferroelectric behavior of KNN-based single crystals. Ta or Sb substitutions indicates that enhanced electromechanical response is achieved when the orthorhombic-tetragonal phase transition is near room temperature. Thermal treatment in pure O2 atmosphere resulted in a twofold increase of the piezoelectric coefficient and ferroelectric parameters of a (K,Na,Li)(Ta,Nb,Sb)O3 single crystal. The highest room-temperature piezoelectric coefficient in annealed KNN-based single crystals of 732 pC/N was obtained. The third approach, doping with Mn ions in (K,Na,Li)(Ta,Nb)O3 single crystals, is also presented.

La définition d'une métrique entre des séries temporelles est un élément important pour de nombreuses tâches en analyse ou en fouille de données, tel que le clustering, la classification ou la prédiction. Les séries temporelles présentent naturellement différentes caractéristiques, que nous appelons modalités, sur lesquelles elles peuvent être comparées, comme leurs valeurs, leurs formes ou leurs contenus fréquentielles. Ces caractéristiques peuvent être exprimées avec des délais variables et à différentes granularités ou localisations temporelles - exprimées globalement ou localement. Combiner plusieurs modalités à plusieurs échelles pour apprendre une métrique adaptée est un challenge clé pour de nombreuses applications réelles impliquant des données temporelles. Cette thèse propose une approche pour l'Apprentissage d'une Métrique Multi-modal et Multi-scale (M2TML) en vue d'une classification robuste par plus proches voisins. La solution est basée sur la projection des paires de séries temporelles dans un espace de dissimilarités, dans lequel un processus d'optimisation à vaste marge est opéré pour apprendre la métrique. La solution M2TML est proposée à la fois dans le contexte linéaire et non-linéaire, et est étudiée pour différents types de régularisation. Une variante parcimonieuse et interprétable de la solution montre le potentiel de la métrique temporelle apprise à pouvoir localiser finement les modalités discriminantes, ainsi que leurs échelles temporelles en vue de la tâche d'analyse considérée. L'approche est testée sur un vaste nombre de 30 bases de données publiques et challenging, couvrant des images, traces, données ECG, qui sont linéairement ou non-linéairement séparables. Les expériences montrent l'efficacité et le potentiel de la méthode M2TML pour la classification de séries temporelles par plus proches voisins. / The definition of a metric between time series is inherent to several data analysis and mining tasks, including clustering, classification or forecasting. Time series data present naturally several characteristics, called modalities, covering their amplitude, behavior or frequential spectrum, that may be expressed with varying delays and at different temporal granularity and localization - exhibited globally or locally. Combining several modalities at multiple temporal scales to learn a holistic metric is a key challenge for many real temporal data applications. This PhD proposes a Multi-modal and Multi-scale Temporal Metric Learning (M2TML) approach for robust time series nearest neighbors classification. The solution is based on the embedding of pairs of time series into a pairwise dissimilarity space, in which a large margin optimization process is performed to learn the metric. The M2TML solution is proposed for both linear and non linear contexts, and is studied for different regularizers. A sparse and interpretable variant of the solution shows the ability of the learned temporal metric to localize accurately discriminative modalities as well as their temporal scales.A wide range of 30 public and challenging datasets, encompassing images, traces and ECG data, that are linearly or non linearly separable, are used to show the efficiency and the potential of M2TML for time series nearest neighbors classification.

Made available in DSpace on 2014-12-17T14:55:45Z (GMT). No. of bitstreams: 1 JannaynaDB_DISSERT.pdf: 1591261 bytes, checksum: c15fb1758e21a5e052a25aed22b0a0db (MD5) Previous issue date: 2010-08-13 / Conselho Nacional de Desenvolvimento Cient?fico e Tecnol?gico / This paper proposes a method based on the theory of electromagnetic waves reflected to evaluate the behavior of these waves and the level of attenuation caused in bone tissue. For this, it was proposed the construction of two antennas in microstrip structure with resonance frequency at 2.44 GHz The problem becomes relevant because of the diseases osteometabolic reach a large portion of the population, men and women. With this method, the signal is classified into two groups: tissue mass with bony tissues with normal or low bone mass. For this, techniques of feature extraction (Wavelet Transform) and pattern recognition (KNN and ANN) were used. The tests were performed on bovine bone and tissue with chemicals, the methodology and results are described in the work / Este trabalho prop?e um m?todo baseado na teoria das ondas eletromagn?ticas refletidas para avaliar o comportamento dessas ondas e o n?vel de atenua??o provocada no tecido ?sseo. Para isto, foi proposta a confec??o de duas antenas em estrutura de microfita com freq??ncia de resson?ncia em 2.44 GHz. O problema torna-se relevante pelo fato das doen?as Osteometab?licas atingirem uma grande parcela da popula??o, entre homens e mulheres. Com esse m?todo, classifica-se os sinais em dois grupos: tecido com massa ossea normal ou tecidos com baixa massa ?ssea. Para isto, t?cnicas de extra??o de caracter?sticas (Transformada Wavelet) e de reconhecimento de padr?es (KNN e RNA) foram usados. Os testes foram realizados em tecido osso bovino e com elementos qu?micos, a metodologia aplicada e resultados obtidos s?o descritos no trabalho

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / Nesta dissertaÃÃo foi estudado o problema de processar consultas kNN em redes de rodovias considerando o histÃrico das condiÃÃes de trÃfego, em particular o caso onde a velocidade dos objetos mÃveis depende do tempo. Dado que um usuÃrio està em uma dada localizaÃÃo e em um determinado instante de tempo, a consulta retorna os k pontos de interesse (por exemplo, postos de gasolina) que podem ser alcanÃados em uma quantidade de tempo mÃnima considerando condiÃÃes histÃricas de trÃfego. SoluÃÃes anteriores para consultas kNN e outras consultas comuns em redes de rodovia estÃticas nÃo funcionam quando o custo das arestas (tempo de viagem) à dependente do tempo. A construÃÃo de estratÃgias e algoritmos eficientes e corretos, e mÃtodos de armazenamento e acesso para o processamento destas consultas à um desafio desde que algumas das propriedades de grafos comumente supostas em estratÃgias para redes estÃticas nÃo se mantÃm para redes dependentes do tempo. O mÃtodo proposto aplica uma busca A∗ à medida que vai, de maneira incremental, explorando a rede. O objetivo do mÃtodo à reduzir o percentual da rede avaliado na busca. Para dar suporte à execuÃÃo do algoritmo, foi tambÃm proposto um mÃtodo para armazenamento e acesso para redes dependentes do tempo. A construÃÃo e a corretude do algoritmo sÃo discutidas e sÃo apresentados resultados experimentais com dados reais e sintÃticos que mostram a eficiÃncia da soluÃÃo. / In this dissertation we study the problem of processing k-nearest neighbours (kNN)queries in road networks considering the history of traffic conditions, in particular the case where the speed of moving objects is time-dependent. For instance, given that the user is at a given location at a certain time, the query returns the k points of interest (e.g., gas stations) that can be reached in the minimum amount of time. Previous solutions to answer kNN queries and others common queries in road networks do not work when the moving speed in each road is not constant. Building efficient and correct approaches and algorithms and storage and access schemes for processing these queries is a challenge because graph properties considered in static networks do not hold in the time dependent case. Our approach uses the well-known A∗ search algorithm by applying incremental network expansion and pruning unpromising vertices. The goal is reduce the percentage of network assessed in the search. To support the algorithm execution, we propose a storage and access method for time-dependent networks. We discuss the design and correctness of our algorithm and present experimental results that show the efficiency and effectiveness of our solution.