196,755 research outputs found
Representing graphs implicitly using almost optimal space
No full textHow to represent a graph in memory is a fundamental data-structuring problem. In the usual representations, a graph is stored by representing explicitly all vertices and all edges. The names (labels) assigned to vertices are used only to encode the edges and reveal nothing about the structure of the graph itself and hence are a "waste" of space. In this context, we present a general framework for labeling any graph so that adjacency between any two given vertices can be tested in constant time. The labeling scheme assigns to each vertex x a O(delta (x) log(2) n) bit label, where n is the number of vertices and delta (x) is x's degree. The adjacency test can be performed in seven steps and the scheme can be computed in polynomial time. The proposed graph encoding positively demonstrates its superiority over the usual representations, i.e. adjacency matrix and adjacency list representations, which require O(n log n) bit label per vertex and constant time adjacency test, and O(delta (x)log n) bit label per vertex and O(log delta (x)) steps to test adjacency, respectively. Additionally, the labeling scheme is implicit, that is: no pointers are used. (C) 2001 Elsevier Science B.V. All rights reserved
An Efficient Data Structure for Lattice Operations
No full textIn this paper, we consider the representation and management
of an element set on which a lattice partial order relation
is defined.
In particular, let
be the element set size, we present
an \nradn-space {\em implicit} data
structure for performing the
following set of basic operations:
\begin {itemize}
\item[1.] test the presence of an order relation between two given elements, in constant time;
\item[2.] find a path between two elements whenever one exists, in
steps, where
is the path length;
\item[3.] compute the successors and/or predecessors set of a given element,
in steps, where
is the size of the returned set;
\item[4.] given two elements, find all elements between them,
in time , where is the size of the returned set and
is the maximum indegree or outdegree in the transitive reduction of the
order relation;
\item[5.] given two elements, find the least common ancestor and/or the greatest common
successor in -time;
\item[6.] given elements, find the least common ancestor and/or the greatest common
successor in
\footnote{Unless stated otherwise, all logarithms are to the base 2.}-time.
\end {itemize}
The pre-processing time is
.
Focusing on the first operation, representing the building-box for all the others, we derive an overall
\nradn-spacetime bound which beats the order bottle-neck representing the present
complexity for this problem. Moreover, we will show that the complexity
bounds for the first three operations are optimal with
respect to the worst case. Additionally, a stronger result can be
derived. In particular, it is possible to represent a lattice in space
, where is the minimum number of disjoint chains which
partition the element set
Efficient data structure for lattice operations
No full textIn this paper, we consider the representation and management of an element set on which a lattice partial order relation is defined. In particular, let n be the element set size. We present an O(n root n)-space implicit data structure for performing the following set of basic operations: 1. Test the presence of an order relation between two given elements, in constant time. 2. Find a path between two elements whenever one exists, in O(l) steps, where l is the path length. 3. Compute the successors and/or predecessors set of a given element, in O(h) steps, where h is the size of the returned set. 4. Given two elements, find all elements between them, in time O(k log d), where k is the size of the returned set and d is the maximum in-degree or out-degree in the transitive reduction of the order relation. 5. Given two elements, find the least common ancestor and/or the greatest common successor in O(root n)-time. 6. Given k elements, find the least common ancestor and/or the greatest common successor in O(root n + k log n)time. (Unless stated otherwise, all logarithms are to the base 2.) The preprocessing time is O(n(2)). Focusing on the first operation, representing the building-box for all the others, we derive an overall O(n root n)-space x time bound which beats the order n(2) bottleneck representing the present complexity for this problem. Moreover, we will show that the complexity bounds for the first three operations are optimal with respect to the worst case. Additionally, a stronger result can be derived. In particular, it is possible to represent a lattice in space O(n root t), where t is the minimum number of disjoint chains which partition the element set
A Data Structure for Lattices Representation.
No full textIn this paper, we present an implicit data structure for the
representation of a partial lattice which
allows to test the partial order relation among two given elements in
constant time.
The data structure proposed has an
overall -space complexity, where is the size of ground
set ,
which we will prove to be optimal in the worst case.
Hence, we derive an overall
-space*time bound for the relation testing problem so beating the bottle-neck
representing the present complexity.
The overall pre-processing time is
Efficient searching for multi-dimensional data made simple
No full textWe introduce an innovative decomposition technique which reduces a multi-dimensional searching problem to a sequence of one-dimensional problems, each one easily manageable in optimal timer space complexity using traditional searching strategies. The reduction has no additional storage requirement and the time complexity to reconstruct the result of the original multi-dimensional query is linear in the dimension. More precisely, we show how to preprocess a set of S subset of or equal to INd of multi-dimensional objects into a data structure requiring O(mlogn) space, where m = \S\ and n is the maximum number of different values for each coordinate. The obtained data structure is implicit, i.e. does not use pointers, and is able to answer the exact match query in 7(d - 1) steps. Additionally the model of computation required for querying the data structure is very simple; the only arithmetic operation needed is the addition and no shift operation is used. The technique introduced, overcoming the multi-dimensional bottleneck, can be also applied to non traditional models of computation as external memory, distributed, and hierarchical environments. Additionally, we will show how the proposed technique permits the effective realizability of the well known perfect hashing techniques on real data. The algorithms for building the data structure are easy to implement and run in polynomial time
ASMA BRONCHIALE E RINITE ALLERGICA: RUOLO DEL RECETTORE ST2 SUI LINFOCITI T HELPER 2
No full textAsma bronchiale e rinite allergica: ruolo del recettore ST2 sui linfociti T helper 2
Introduzione: Secondo recenti ricerche i linfociti T helper 2 (Th2) sono coinvolti nello stato infiammatorio cronico associato all'asma bronchiale e alla rinite allergica (1). Un ruolo importante nella patogenesi è stato attribuito alla produzione epiteliale di alcune nuove citochine, come l’IL-17A e l’IL-33 con il suo peculiare recettore ST2 espresso selettivamente sulle cellule Th2 (2,3). L’IL-17A e l’IL-33 sono implicate nell’indurre l’infiammazione Th2 dipendente della mucosa bronchiale e nasale innescando la produzione di altre citochine infiammatorie tra cui l’IL-31(4).
Materiali e Metodi: Campioni di plasma sono stati raccolti da pazienti con rinite allergica, da pazienti con comorbidità asma/rinite e da soggetti controllo, reclutati per lo studio in seguito ad anamnesi fisiopatologica, intervista preliminare, spirometria e Prick Test. Le concentrazioni plasmatiche dell’IL-31, dell’IL-33 e dell’IL-17A sono state misurate con dosaggio ELISA. Inoltre, l’IL-17A, l’IL-31 e il recettore ST2 sono stati acquisiti e valutati mediante analisi al citofluorimetro sui PBMC isolati dal sangue periferico di alcuni dei suddetti pazienti. Infine, si è proceduto alla valutazione dell’attività in vitro di uno steroide, il Beclometasone Dipropionato (BDP) (10−8M e 10−7M), sull’espressione delle citochine intracellulari IL-17A e IL-31 in associazione con il recettore ST2 in colture di PBMCs.
Risultati: È stato osservato che i livelli plasmatici di IL-17A, IL-31 e IL-33 sono aumentati in maniera statisticamente significativa sia nei pazienti con rinite allergica che nei pazienti con comorbidità asma/rinite rispetto ai controlli. I dati ottenuti dall'analisi al citofluorimetro hanno rivelato incrementi statisticamente significativi di espressione delle citochine intracellulari IL-17A e IL-31 in ognuno dei gruppi di pazienti allergici rispetto al gruppo controllo. Allo stesso tempo, i livelli di espressione del recettore ST2 sulle cellule degli stessi pazienti sono risultati considerevolmente più bassi rispetto ai controlli. Infine, è stato osservato che il BDP riduce significativamente i livelli intracellulari di IL-17A e di IL-31 nei PBMCs di questi pazienti in confronto alla baseline e che, per quanto riguarda invece l’espressione del recettore ST2 sulla membrana delle cellule T, è stato riscontrato un aumento dose-dipendente, che diventa significativo alla concentrazione di BDP 10-7M.
Conclusioni: In base ai dati sperimentali ottenuti, si è potuto quindi concludere che esiste una correlazione tra l’aumento di IL-17A, l’attivazione dell’asse IL-33/ST2 e l’incremento di IL-31 nell’asma bronchiale e nella rinite allergica e che queste tre nuove citochine potrebbero quindi rappresentare dei validi biomarcatori valutabili per la patogenesi e per la diagnosi di asma e rinite. Infine, i risultati di questo studio hanno supportato il potenziale approccio terapeutico mediante l’impiego di BDP nel controllo dell’infiammazione locale e sistemica, generata dalla risposta immunitaria Th2- e Th17-mediata, in pazienti con malattie infiammatorie allergiche delle vie aeree.
1. Saenz SA et al. IL25 elicits a multipotent progenitor cell population that promotes T(H)2 cytikine responses. Nature. 2010;464(7293):1362-6.
2. Glück J. et al. Serum IL-33 but not ST2 level is elevated in intermittent allergic rhinitis and is a marker of the disease severity. Inflamm. Res. 2012;61:547-550.
3. Kamekura R. et al. The role of IL-33 and its receptor ST2 in human nasal epithelium with allergic rhinitis. Clin. Exp.Allergy. 2012;42(2):218-228.
4. Okano M. et al. Characterization of pollen antigen-induced IL-31 production by PBMCs in patients with allergic rhinitis. JACI. 2010;127(1):277-9.Bronchial Asthma and Allergic Rhinitis: Role of ST2 receptor on T helper 2 lymphocytes.
Introduction: T helper 2 (Th2) lymphocytes play an important role in the chronic inflammatory process concerning bronchial asthma and allergic rhinitis (1), regulating the production of some new cytokines, IL-17A and IL-33 with ST2 receptor, selectively expressed on the Th2 cells surface (2, 3), by the airway epithelium. IL-17A and IL-33 are involved in the Th2 cells-mediate induction of the bronchial and nasal mucosa inflammation, triggering the production of more inflammatory cytokines, including IL-31 (4).
Materials and Methods: Plasma samples from allergic rhinitis, both asthma and rhinitis patients and control subjects were collected. These subjects were recruited for this study following pathophysiological history, preliminary interview, spirometry and Prick Test. Plasma concentrations of IL-31, IL-33 and IL-17A were measured by ELISA. Also, IL-17A, IL-31 and ST2 receptor were evaluated by flow cytometric analysis on peripheral blood mononuclear cells (PBMC) of some of these patients. After all, the in vitro activity of a steroidal drug, Beclomethasone Dipropionate (BDP) (10−8M e 10−7M), was evaluated on the intracellular cytokines IL-17A and IL-31 expression, together with ST2 receptor levels in PBMCs cultures.
Results: IL-17A, IL-31 e IL-33 plasma levels were significantly higher in patients with allergic rhinitis and in those with both asthma and rhinitis than in control subjects. Flow cytometer data show that the expression of the intracellular cytokines IL-31 and IL-17A were increased in all patients categories compared to controls. At the same time, ST2 receptor expression levels, on T cells surface of these same patients, were significantly lower than those in control subjects. Finally, has been observed that BDP substantially decreases intracellular levels of IL-17A and IL-31 cytokines in PBMCs of these patients compared to baseline. Rather, the ST2 receptor surface expression was increased in a dose-dependent manner and, significantly, at BDP concentration 10-7M.
Conclusions: In the present study, the experimental data suggest that there is a correlation between higher levels of IL-17A, activation of IL-33/ST2 axis and increased concentration of IL-31 in bronchial asthma and allergic rhinitis and that these three new cytokines could therefore represent valid biomarkers evaluable in the pathogenesis and diagnosis of both diseases. At last, the results of this study supported the potential therapeutic approach by BDP in local and systemic inflammation control, of Th2 and Th17 immune response, in patients with inflammatory diseases of allergic airways.
1. Saenz S.A. et al. IL25 elicits a multipotent progenitor cell population that promotes T(H)2 cytokine responses. Nature. 2010;464(7293):1362-6.
2. Glück J. et al. Serum IL-33 but not ST2 level is elevated in intermittent allergic rhinitis and is a marker of the disease severity. Inflamm. Res. 2012;61:547-550.
3. Kamekura R. et al. The role of IL-33 and its receptor ST2 in human nasal epithelium with allergic rhinitis. Clin. Exp.Allergy. 2012;42(2):218-228.
4. Okano M. et al. Characterization of pollen antigen-induced IL-31 production by PBMCs in patients with allergic rhinitis. JACI. 2010;127(1):277-9
- …
